Mock CCO '18 Contest 2 Problem 5 - Victor's Triangles

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

Roger was unable to tilt Victor with rectangles, so now he's going to try with triangles instead!

Roger has given Victor a triangulation of a convex polygon with N sides. The polygon has already been triangulated by Roger, and every triangle has been filled in with some color. The vertices are randomly labeled with distinct positive integers from 1 to N.

Roger challenges Victor to draw as many line segments connecting points on the border of the polygon such that, for every color present on the polygon, that color only appears in exactly one region defined by the polygon and the line segments that Victor has drawn.

Compute the maximum number of segments that Victor can draw respecting the above constraint.

Constraints

3N105

1ai,bi,ci,diN

The triangulation provided in the input will correspond to a valid triangulation of some polygon with N sides.

Subtask 1 [50%]

N5103

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line will contain a single integer, N.

Each of the next N2 lines will contain four space-separated integers, ai, bi, ci, and di, indicating that the triangle with vertices ai, bi, ci, is colored with color di.

Output Specification

Print, on a single line, the maximum number of line segments Victor can draw.

Sample Input 1

Copy
5
1 2 3 2
4 5 1 1
3 1 4 2

Sample Output 1

Copy
1

Sample Input 2

Copy
6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

Sample Output 2

Copy
0

Comments

There are no comments at the moment.