Mock CCC '20 Contest 2 S3 - Tree Programming

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Ninjaclasher

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$ $N$ nodes and $M$ $M$ edges. Edge $i$ $i$ connects nodes $u_i$ $u_{i}$ and $v_i$ $v_{i}$ with a value of $k_i$ $k_{i}$ . A path from $a_j$ $a_{j}$ to $b_j$ $b_{j}$ consists of a sequence of the $M$ $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$ $Q$ queries, $a_j, b_j$ $a_{j}, b_{j}$ , can you determine the minimum path value of a path from $a_j$ $a_{j}$ to $b_j$ $b_{j}$ ?

Input Specification

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

The next $M$ $M$ lines will each contain three integers, $u_i, v_i, k_i$ $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)$ $(1 \leq u_{i}, v_{i} \leq N, u_{i} \neq v_{i}, 0 \leq k_{i} \leq 100)$ , indicating there is an edge between nodes $u_i$ $u_{i}$ and $v_i$ $v_{i}$ of value $k_i$ $k_{i}$ . Note that there may be duplicate edges between nodes. It is guaranteed that the entire graph is connected.

The next $Q$ $Q$ lines will each contain two integers, $a_j, b_j$ $a_{j}, b_{j}$ $(1 \le a_j, b_j \le N, a_j \neq b_j)$ $(1 \leq a_{j}, b_{j} \leq 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$ $k_{i} \leq 1, N \leq 10, M \leq 20$ .

For an additional 3/15 of the points, $k_i \le 1$ $k_{i} \leq 1$ .

Sample Input 1

Copy

Sample Output 1

Copy

0
0

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

Sample Input 2

Copy

Sample Output 2

Copy

Comments

0

III commented on Feb. 2, 2023, 12:08 a.m. ← edited →

What's the point of k?

Edit: Nvm, I just read the text again and yeah.

-1

satvick16 commented on Feb. 5, 2021, 1:42 p.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!

2

ZZXZZX commented on Feb. 7, 2021, 3:42 a.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