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

View as PDF

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, and .

#### Input Specification

The first line will contain two space-separated integers, and , indicating respectively the number of vertices and the number of edges in the graph.

The next lines will contain three space-separated integers , and , indicating that edge is an undirected weighted edge between vertices and with weight . There may be multiple edges between two vertices.

The next line contains a single integer , the number of operations to support.

Each of the next 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 .

A query will take the form 2 a_i b_i w_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.

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

0
1
1
0