All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef was practicing with some graph theory problems in CodeChef. He was trying to solve a problem involving finding the shortest path in a weighted, undirected graph. He thought it was quite standard, so he coded the solution and submitted it. Unfortunately it was judged “Wrong Answer”.
Wanting to debug, Chef downloaded Peter Xor's accepted solution. He also made a test case, illustrated by the following image:
Now, what is the cost of the shortest path from 1 to 5? Chef thought that the answer should be 36 + 16 + 18 = 70, because the other candidate path has a higher total cost of 36 + 50 + 11 + 18 = 115. But he was surprised when Peter Xor's accepted solution outputted 15! Chef was confused because he can't see any path with a total cost of 15.
After rereading the problem, Chef found his mistake. The problem's title was actually Xortest path, not Shortest path, so the problem was actually asking for the path between two given nodes with the least possible XOR! So in the example above, the answer is indeed 15, because the path 1 → 2 → 3 → 4 → 5 has an XOR cost of 36 ⊕ 50 ⊕ 11 ⊕ 18 = 15, and no other path has a lower XOR cost than this. In other words, this is the “xortest path”.
Now that Chef knows his mistake, he still has a problem; he doesn't know how to answer this problem! Your task as his sous-chef is to answer this problem for him. Specifically, you have to answer Q queries, where each query is a pair of nodes, and the answer is the weight of the “xortest path” between them.
Note that in this problem, a path may pass through an edge or node any number of times. (Some authors would call such a path a walk.) For instance, in the example above, the path 1 → 2 → 4 → 3 → 2 → 4 → 5 is also a “xortest path”, because its XOR cost is 36 ⊕ 16 ⊕ 11 ⊕ 50 ⊕ 16 ⊕ 18 = 15.
The first line of input contains three integers, N, E and Q. Nodes are labelled 1 to N.
The following E lines describe the edges. The ith line contains three integers ai, bi and ci, which means that there is an undirected edge between nodes ai and bi with weight ci.
The following Q lines describe the queries. The jth line contains two integers xj and yj, which means that you need to find the “xortest path” between nodes xj and yj.
Output Q lines, one for each query. The jth line must contain a single integer, the weight of the xortest path between xj and yj. If there does not exist a path between these nodes, output “XIT” (without quotes) instead.
- 1 ≤ N, E, Q ≤ 105
- 1 ≤ ai, bi, xj, yj ≤ N
- 0 ≤ ci ≤ 109
- Parallel edges or self-loops may appear.
Input: 7 7 5 1 2 36 2 4 16 4 5 18 2 3 50 3 4 11 6 6 100 7 6 100 1 5 5 1 1 2 6 7 1 7 Output: 15 15 13 0 XIT
The sample input is illustrated by the image above.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.