P6677 [COCI 2019/2020 #2] Checker

> "...fool me once, shame on — shame on you. Fool me — you can't get fooled again." — W

There is a regular polygon whose $n$ sides are colored using one of three colors, and its vertices are labeled from $1$ to $n$ in clockwise order. A triangulation of the polygon means decomposing its area into a set of non-overlapping triangles, where the sides of these triangles can be polygon sides or interior diagonals. Of course, in this task, every diagonal used in the triangulation is also colored with one of the three colors. Such a triangulation is called “very good” if, for each of the $n - 2$ triangles, all three of its sides have different colors. Your task is to determine whether the given polygon with its diagonals is correctly triangulated, and whether that triangulation is very good.

The input has $n$ lines. The first line contains a positive integer $T$, which indicates the Subtask number for this test. The second line contains a positive integer $n$, as described in the **Description** section. The third line contains a positive integer with $n$ digits. These digits represent the colors of the polygon sides. More precisely, the first digit represents the color of side $(1, 2)$, the second digit represents the color of side $(2, 3)$, the $i$-th digit represents the color of side $(i, i+1)$, and **in particular**, the $n$-th digit represents the color of side $(n, 1)$. Colors are denoted by digits $1, 2, 3$. The next $n - 3$ lines each contain a description of a diagonal in the format `x y c`, where $x$ and $y$ are polygon vertices, and $c$ is the color of the diagonal. The input guarantees that vertices $x$ and $y$ are neither equal nor adjacent.

Output one line. - If the input polygon is not correctly triangulated, output $\mathtt{neispravna \space triangulacija}$. - If the input polygon has a correct triangulation, but the triangulation is not good, output $\mathtt{neispravno \space bojenje}$. - Otherwise, output $\mathtt{tocno}$.

#### Constraints and Notes This problem uses **bundled tests**. | Subtask Number | Subtask Score | Constraints and Notes | | :----------- | :----------- | :----------- | | $1$ | $12$ | $4 \le n \le 300$ | | $2$ | $17$ | $4 \le n \le 2000$ | | $3$ | $23$ | $4 \le n \le 2 \times 10^5$, the testdata guarantees the output is $\mathtt{neispravna \space triangulacija}$ or $\mathtt{tocno}$ | | $4$ | $23$ | $4 \le n \le 2 \times 10^5$, the testdata guarantees the output is $\mathtt{neispravno \space bojenje}$ or $\mathtt{tocno}$ | | $5$ | $35$ | $4 \le n \le 2 \times 10^5$ | **In particular**, for $100\%$ of the testdata, $1 \le T \le 5$. #### Notes **The scoring of this problem follows the original COCI problem setting, with a total of $110$ points.** **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T3 Checker*.** Translated by ChatGPT 5