sherlock_holms's blog

By sherlock_holms, history, 7 years ago, In English

Problem link : http://codeforces.me/contest/763/problem/E

I am debugging my solution against already accepted solutions for this problem, by creating large test cases. I have found something weird. Some solutions are considering even the trees which are either (< l) or (> r). I have one testcase which proves this.

testcase link : https://drive.google.com/file/d/0B088hEdwtfVCSG5KNTl1M3REdUk/view?usp=sharing -> Query is (35916, 35926). you can check from the relation ship edges (by running a loop on them) that there are only three relationship edges which are useful for this query which are [(35922, 35924), (35923, 35925), (35925, 35926)]. using this answer will be 8, but answer from accepted solutions is 9. Even manually answer is 8. Can someone please explain the problem here ?

here is link to my solution : http://codeforces.me/contest/763/submission/27576175

Tags dsu
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sherlock_holms (previous revision, new revision, compare).