All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
For a given connected graph G with N vertices and M undirected weighted edges, the goal is to perform Q queries, each belonging to one of the below 3 types:
- AssignZero(u, v) := Change the weight of edge between vertices u and v to zero. It is guaranteed there is an edge between vertex u and v in the graph G.
- AssignOriginal(u, v) := Change the weight of edge between vertices u and v to its original weight.
- MstWeight() := Returns the weight of Minimal Spanning Tree of G.
First line of the input contains three space separated integers N, M and Q, denoting the number of vertices in G, the number of edges in G, and the number of queries to perform, respectively.
Next M lines follow, each consisting of three space separated integers u, v and w, denoting that there is an edge between vertices u and v in G of weight w.
The i-th of the following Q lines corresponds to the i-th query. It starts with a single integer qtype denoting the type of the query. If qtype = 1 or 2, it is followed by two space separated integers u, v denoting the arguments of the query.
For each query of type 3, output an integer in a single line corresponding to the answer to this query.
- 1 ≤ v, u ≤ N
- v ≠ u
- 1 ≤ w ≤ 109
- 1 ≤ qtype ≤ 3
- There are no multi-edges and no self loops in the graph G.
- For every query of types 1 and 2, it is guaranteed that there is an edge between vertices u and v in G.
Subtask #1: (20 points)
- 2 ≤ N ≤ 200
- 1 ≤ M ≤ 2000
- 1 ≤ Q ≤ 2000
Subtask #2: (50 points)
- 2 ≤ N ≤ 2000
- 1 ≤ M ≤ 2*105
- 1 ≤ Q ≤ 2*104
- There is no query of type 2
Subtask #3: (30 points)
- The same as in subtask #2, but all query types are allowed
Input: 4 4 5 1 2 1 2 3 1 3 4 1 4 1 1 3 1 1 2 3 2 1 2 3 Output: 3 2 3
The input graph has 4 vertices and 4 edges, it can be drawn like this:
4_____3 | | | | |_____ | 1 2
Initially, all edges have weight equal 1. There are 5 queries to handle.
In the first query, we are asked for the weight of Minimal Spanning Tree, which is 3 (taking any 3 edges produces such a tree).
After that, weight of edge between vertices 1 and 2 is changed to 0. Then we are asked again for the weight of Minimal Spanning Tree. It is now 2, because we can take edge from 1 to 2 and any 2 of the remaining edges.
Next, we restore the weight of edge between vertices 1 and 2, i.e. change it to original weight 1. Finally, we are again asked for the weight of Minimal Spanning Tree, which is again 3, because the underlying graph is the same as it was at the beginning.
|Tags||graph, kruskal, ltime43, medium, mst, pkacprzak|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.