DMOPC '19 Contest 5 P5 - Crazy Cyclic Coincidences

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 3.0s
Memory limit: 128M
Python 256M

Problem type

Like his fellow conspiracy theorists, Shoievel likes to waste his time finding "coincidences" to come up with some ridiculously convoluted proof that aliens exist. In his efforts to fool the general public, he has come to study the layout of cities in Wielxiez. Wielxiez has N different cities that are connected by M roads, each of them of integer length. For some reason, Shoievel believes that the value of a path taken through Wielxiez is equal to the XOR-sum of all the roads taken. To add to this ridiculousness, Shoievel believes that by finding any path that begins and ends at the same city amongst the cities and roads of Wielxiez with a value of V, he will complete his indisputable proof that aliens exist. Since this maniac has enslaved you, you must now determine whether or not Shoievel can complete his proof.

Input Specification

The first line contains three space-separated integers, N, M, and V.
M lines follow, each of which contains three space-separated integers, u_i, v_i, and l_i, describing a road between city u_i and city v_i with length l_i.
It is guaranteed that it is possible to get from any city to any other city in Wielxiez using only the roads described.

Output Specification

Output yes if there exists a path that begins and ends at the same city with a value of V. Otherwise, output no.


In all subtasks,
1 \le N,M \le 500\,000
0 \le V,l_i < 2^{20}

Subtask 1 [10%]

The cities and roads of Wielxiez form at most one cycle.

Subtask 2 [20%]

N,M \le 20

Subtask 3 [70%]

No additional constraints.

Sample Input 1

5 7 1
3 4 6
4 5 5
4 2 3
5 4 0
3 3 7
2 4 6
1 2 6

Sample Output 1


Sample Input 2

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

Sample Output 2



There are no comments at the moment.