NOI '15 P1 - Automated Program Analyzer

View as PDF

Submit solution

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

Problem type

Let x_1, x_2, x_3, \dots be variables. n constraints of form x_i = x_j or x_i \ne x_j are given. The task asks for whether it is possible to assign values to the variables so that all constraints can be satisfied. For example, if the constraints are x_1 = x_2, x_2 = x_3, x_3 = x_4, x_1 \ne x_4, then those constraints cannot be satisfied simultaneously.

Input Specification

The first line of the input is an integer t representing the number of instances to solve. The instances are independent. For each instance, the first line is an integer n representing the number of constraints to be satisfied. In the following n lines, each line has three integers i,j,e representing an equality/inequality constraint. If e = 1, the constraint shall be x_i = x_j. If e = 0, the constraint shall be x_i \ne x_j.

Output Specification

The output has t lines. The k-th line of the output is a string YES or NO. Output YES if the constraints in that instance can be satisfied and NO otherwise.

Sample Input 1

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

Sample Output 1

NO
YES

Sample Input 2

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

Sample Output 2

YES
NO

Constraints

Test Caseni, jAdditional Constraints
11\le n\le 101\le i,j\le 10\,0001\le t\le 10, e\in\{0,1\}
2
31\le n\le 100
4
51\le n\le 100\,000
6
7
81\le n\le 100\,0001\le i,j\le 1\,000\,000\,000
9
10

Comments

There are no comments at the moment.