Need help in a graph problem from the Live Archive

Revision en3, by Robin, 2019-09-15 09:37:16

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/tfhFWN8hZj/

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.

What did I do wrong?

Tags mst, #graph, lca

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English 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 English Robin 2019-09-15 09:34:35 24 Tiny change: 'iven road.' -> 'iven road.\n\nWhat did I do wrong?'
en1 English Robin 2019-09-15 09:26:20 957 Initial revision (published)