CCO Preparation Test 4 P3 - Dynamic MST - DMOJ: Modern Online Judge

CCO Preparation Test 4 P3 - Dynamic MST

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.8s

Memory limit: 128M

Author:

bruce

Problem type

Given $N$ $N$ vertices and $M$ $M$ weighted bidirectional edges, Bruce knows how to find the Minimal Spanning Tree (MST). But if the weight of each edge is changing, Bruce doesn't know how to efficiently find the MST after each change. Can you write a program to help Bruce?

Input Specification

The first line of input will consist of three integers, $N$ $N$ , $M$ $M$ and $Q$ $Q$ , which are the number of vertices, number of edges, and number of weight changes.

Each of the next $M$ $M$ lines will consist of three integers, $x$ $x$ , $y$ $y$ and $z$ $z$ ( $1 \le x, y \le N$ $1 \leq x, y \leq N$ , $0 \le z \le 50\,000\,000$ $0 \leq z \leq 50 000 000$ ), which represents the bidirectional edge between $x$ $x$ and $y$ $y$ has the cost $z$ $z$ .

Each of the next $Q$ $Q$ lines will consist of two integers, $k$ $k$ and $d$ $d$ ( $1 \le k \le M$ $1 \leq k \leq M$ , $0 \le d \le 50\,000\,000$ $0 \leq d \leq 50 000 000$ ), which represents the $k-$ $k -$ th edge's cost changes to $d$ $d$ .

Output Specification

Output $Q$ $Q$ lines. The line $k$ $k$ consists of 1 integer, the cost of MST after the first $k$ $k$ changes.

Constraints

20% cases $N \le 1\,000$ $N \leq 1 000$ , $M \le 6\,000$ $M \leq 6 000$ , $Q \le 6\,000$ $Q \leq 6 000$ .

40% cases $N \le 1\,000$ $N \leq 1 000$ , $M \le 50\,000$ $M \leq 50 000$ , $Q \le 8\,000$ $Q \leq 8 000$ .

100% cases $N \le 20\,000$ $N \leq 20 000$ , $M \le 50\,000$ $M \leq 50 000$ , $Q \le 50\,000$ $Q \leq 50 000$ .

Sample Input

Copy

Sample Output

Copy

14
10
9

Comments

13

koosaga commented on Jan. 1, 2018, 2:46 p.m.

What if graph doesn't have minimum spanning tree?

9

Kirito commented on Feb. 26, 2019, 3:36 p.m.

For anyone solving this problem in the future, it is guaranteed that the graph is connected.

12

imaxblue commented on March 15, 2017, 3:09 a.m.

block size 400 is more effective than either block size 500, 200, 250, 125 or 100

4

wleung_bvg commented on Aug. 24, 2017, 8:09 a.m.

It does seem to vary based on the implementation

4

bruce commented on Aug. 24, 2017, 12:40 p.m.

Time complexity is supposed to be $\mathcal{O}(Q \log N \log N)$ $O (Q \log N \log N)$ and time limit is supposed to be 2 sec.