APIO '19 P2 - Bridges

View as PDF

Submit solution

Points: 35 (partial)
Time limit: 1.4s
Memory limit: 512M

Problem type
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

St. Petersburg is located on n islands that are connected by m bridges. Islands are labeled by integers from 1 to n, and bridges — from 1 to m. Every bridge connects two distinct islands. Some bridges were built in Peter the Great era, and some of them were built recently. That's why different bridges have different weight limits. Namely, only the cars with weight not exceeding d_i can drive through the i-th bridge. Sometimes some of the bridges in St. Petersburg are being renovated, but this doesn't necessarily make the bridge stronger, so, some of d_i may either increase or decrease. You develop a product that will help citizens and city guests. Currently, you develop a module that has to answer two types of queries:

  1. The weight limit of bridge b_j became equal to r_j.
  2. Count the number of islands, that can be reached by the car of weight equal to w_j from island s_j.

Answer all queries of the second type.

Note: The official time limit is 2.0s

Input

The first line contains two integers n and m — the number of islands and bridges in St. Petersburg (1 \le n \le 50\,000, 0 \le m \le 100\,000).

The i-th of the following m lines contains three integers u_i, v_i, and d_i that describe the bridge connecting islands u_i and v_i, initially its weight limit equals to d_i (1 \le u_i, v_i \le n; u_i \ne v_i; 1 \le d_i \le 10^9).

The following line contains single integer q — the number of queries (1 \le q \le 100\,000). The following q lines contain queries.

The description of each query starts with an integer t_j (t_j \in \{1, 2\}).

If t_j = 1, the query is of the first type, then two integers b_j and r_j follow, they mean that the weight limit of the bridge b_j becomes equal to r_j (1 \le b_j \le m, 1 \le r_j \le 10^9).

If t_j = 2, the query is of the second type, then two integers s_j and w_j follow, that describe a car of weight w_j located on island s_j (1 \le s_j \le n, 1 \le w_j \le 10^9).

Output

For each query of the second type print the answer on a separate line.

Scoring

Subtask 1 (points: 13)

n \le 1\,000, m \le 1\,000, q \le 10\,000.

Subtask 2 (points: 16)

Islands and bridges form a chain, m = n - 1, u_i = i, v_i = i + 1 (1 \le i \le m).

Subtask 3 (points: 17)

Islands and bridges form a complete binary tree, n = 2^k-1, m = n-1, u_i = \left \lfloor \frac{i+1}{2} \right \rfloor, v_i = i+1 (1 \le k \le 15, 1 \le i \le m).

Subtask 4 (points: 14)

All t_j equal to 2.

Subtask 5 (points: 13)

Islands and bridges form a tree, m = n - 1.

Subtask 6 (points: 27)

No additional constraint.

Sample Input 1

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

Sample Output 1

3
2
3

Sample Input 2

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3

Sample Output 2

1
7
7
5
7
7
4

Explanation

Green lines represent bridges that the car from the query can drive through. Green vertices represent islands that are reachable by this car. Arrow points to the island, where the car is located initially.

 

 

 


Comments

There are no comments at the moment.