Mock CCC '18 Contest 2 S5 - A Link/Cut Tree Problem

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.4s
Memory limit: 1G

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given a graph, support the following two operations:

Query(a_i, b_i, w_i): Does there exist a path from a_i to b_i using only edges with weight at least w_i?

Update(m_i, x_i): Update the weight of edge m_i to be x_i.

Constraints

For 2 marks, there will be no update operations.

For 3 additional marks, M \le 10^3 and Q \le 10^3.

Input Specification

The first line will contain two space-separated integers, N (1 \le N \le 10^3) and M (1 \le M \le 5000), indicating respectively the number of vertices and the number of edges in the graph.

The next M lines will contain three space-separated integers u_i (1 \le u_i \le N), v_i (1 \le v_i \le N, u_i \neq v_i) and z_i (1 \le z_i \le 10^9), indicating that edge i is an undirected weighted edge between vertices u_i and v_i with weight z_i. There may be multiple edges between two vertices.

The next line contains a single integer Q (1 \le Q \le 10^5), the number of operations to support.

Each of the next Q lines will contain the description of either a query or an update.

An update operation, which can happen at most 2000 times, will take the form 1 m_i x_i (1 \le m_i \le M, 1 \le x_i \le 10^9).

A query will take the form 2 a_i b_i w_i (1 \le a_i, b_i \le N, 1 \le w_i \le 10^9, a_i \neq b_i).

Note that the operations happen in the order specified in the input.

Output Specification

For each query, print on a separate line 1 if the answer to the query is yes, and 0 otherwise.

Sample Input

3 4
1 2 3
2 3 3
2 1 1
1 2 1
6
2 1 2 4
2 2 3 2
1 1 4
2 1 2 4
1 2 1
2 2 3 2

Sample Output

0
1
1
0

Comments

There are no comments at the moment.