dx24816's blog

QTREE5

By dx24816, history, 6 years ago, In English

Hello,

I tried to do QTREE5 (https://www.spoj.com/problems/QTREE5/), but I keep getting WA on test case 5. I'm using Centroid Decomposition, and I'm pretty sure it's correct because I tested it on Codeforces 342E and got AC. That means the error is probably in the closest function, the toggle function, getDist function, or something in the main function. Can somebody point out my error? Thanks!

Code: https://ideone.com/gZ85l8

-dx24816

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Replace (*(cdist[v].rbegin())).first with (*(cdist[v].begin())).first because here we want minimum distance to the node.

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Is it necessary to keep pair in multiset? I am trying the same way(without pair), still WA. Code: https://ideone.com/PpbbXc Could someone take a look?

Edit: AC using pair, what am i missing? shouldn't it work without information of which node caused which value?

Edit: multiset.erase(multiset.find(value)) works.

→ Reply