Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

Robin's blog

By Robin, history, 5 weeks ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I've got WA on LA too and I do not know what's wrong too. You can check your code here and test your I/O here.