Need help in a graph problem from the Live Archive

Правка en1, от Robin, 2019-09-15 09:26:20

Need help with this problem:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=6218

My solution: https://paste.ubuntu.com/p/Sx7gYY5syf/

Verdict: TLE

I used Sparse Table for the LCA and Kruskal for the MST. My actual code starts from line 117, the rest above is template, can be ignored. I commented in each step to explain what I did.

My idea for the solution: I construct MST from the given graph. This way I only repair the roads that yield minimum cost and connects all the cities. Then, for each query, if the given road is already in the MST, we just construct the rest of the roads in the MST. Hence we return the sum of all edges in the MST. Else, if the road is not in the MST, we remove the most costly road (largest weighted edge) along the path from u to v from the MST, and add the given road.

Теги mst, #graph, lca

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Robin 2019-09-15 09:37:16 18 Tiny change: 'ntu.com/p/Sx7gYY5syf/\n\n**Ver' -> 'ntu.com/p/tfhFWN8hZj/\n\n**Ver'
en2 Английский Robin 2019-09-15 09:34:35 24 Tiny change: 'iven road.' -> 'iven road.\n\nWhat did I do wrong?'
en1 Английский Robin 2019-09-15 09:26:20 957 Initial revision (published)