Mock CCC '20 Contest 2 S3 - Tree Programming

View as PDF

Submit solution

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

Author:
Problem type

A tree is a strange type of graph. We will not be dealing with trees today, as they are too hard.

You are instead given a graph of N nodes and M edges. Edge i connects nodes u_i and v_i with a value of k_i. A path from a_j to b_j consists of a sequence of the M edges, such that consecutive edges in the path share a common node. The value of this path is the bitwise OR of all the edge values in the path.

Given Q queries, a_j, b_j, can you determine the minimum path value of a path from a_j to b_j?

Input Specification

The first line will contain three integers N, M, Q (2 \le N \le 5 \times 10^4, N-1 \le M \le 10^5, 1 \le Q \le 10^5).

The next M lines will each contain three integers, u_i, v_i, k_i (1 \le u_i, v_i \le N, u_i \neq v_i, 0 \le k_i \le 100), indicating there is an edge between nodes u_i and v_i of value k_i. Note that there may be duplicate edges between nodes. It is guaranteed that the entire graph is connected.

The next Q lines will each contain two integers, a_j, b_j (1 \le a_j, b_j \le N, a_j \neq b_j).

Output Specification

For each query, output one integer, the minimum path value.

Subtasks

For 2/15 of the points, k_i \le 1, N \le 10, M \le 20

For an additional 3/15 of the points, k_i \le 1

Sample Input 1

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

Sample Output 1

0
0

Note: You do not need to pass sample 2 for subtask 1 or 2.

Sample Input 2

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

Sample Output 2

3
3
1
1
2

Comments


  • 0
    satvick16  commented on Feb. 5, 2021, 8:42 a.m. edit 2

    I might just be stupid, but in the second sample input, if I have calculated correctly, the value of the path should be 2 but it actually shows 1. I think this issue might also be present in the test cases upon submission. If you could let me know what is going on, that would be great. Thanks!


    • 1
      ZZXZZX  commented on Feb. 6, 2021, 10:42 p.m.

      The value of this path is the bitwise OR of all the edge values in the path. Pay attention it's not the sum of the edge values in the path, it's bitwise OR