COCI '19 Contest 2 #3 Checker

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem types

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

In this task, we will observe regular polygons that have each of their N sides coloured in one of three colours and whose vertices are denoted from 1 to N in clockwise order. A triangulation of a polygon is a decomposition of its area into a set of non-overlapping triangles whose sides either lie on the sides of the polygon or its internal diagonals. Of course, in this task, each of the diagonals used for polygon triangulation is also coloured in one of three colours.

The triangulation is said to be patriotic if each of its N-2 triangles has all three sides of different colours. Your task is to determine whether a given polygon with its diagonals is triangulated and whether that triangulation is patriotic.


The first line contains the subtask number this particular test case belongs to (see the table in the scoring section). If your solution doesn't care about that, simply read the number and feel free to ignore it.

The second line contains an integer N from the task description.

The third line contains an integer consisting of N digits which represent the colours of polygon sides. More precisely, the first digit represents the colour of side (1, 2), the second digit represents the colour of side (2, 3), and so on until the N-th digit which represents the colour of side (N, 1). The colours will always be denoted with digits 1, 2 and 3.

Each of the next N-3 lines contain a description of one diagonal in the form X Y C, where X and Y are polygon vertices and C is the colour of the diagonal (1 \le X, Y \le N, 1 \le C \le 3). Each line describes a valid diagonal, i.e., vertices X and Y will neither be equal nor neighbouring.


If the input polygon is not correctly triangulated, you should output neispravna triangulacija (invalid triangulation in Croatian).

If the input polygon is correctly triangulated but the triangulation is not patriotic, you should output neispravno bojenje (invalid colouring in Croatian).

If the input polygon is correctly triangulated and that triangulation is patriotic, you should output tocno (correct in Croatian).


Subtask Score Constraints
1 12 4 \le N \le 300
2 17 4 \le N \le 2000
3 23 4 \le N \le 2 \cdot 10^5, the output is either neispravna triangulacija or tocno
4 23 4 \le N \le 2 \cdot 10^5, the output is either neispravno bojenje or tocno
5 35 4 \le N \le 2 \cdot 10^5

Unlike the task Trobojnica from round 1, if your program correctly outputs the first line in each test case of a certain subtask, you will score 100\% of the points allocated for that subtask.

Sample Input 1

1 3 3
2 5 2

Sample Output 1

neispravna triangulacija

Sample Input 2

1 3 2

Sample Output 2

neispravno bojenje

Sample Input 3

1 3 3
3 5 1
5 7 3
7 3 2

Sample Output 3




There are no comments at the moment.