the_tester_'s blog

By the_tester_, history, 5 years ago, In English

My solution 57636356 to the problem 839C - Journey uses BFS implementation but I am getting a wrong answer on test no.4. Editorial suggests a dfs implementation which is clear enough but I want to know what went wrong in my implementation? Any ideas or sample testcases would be a great help.

Thanks in advance!!

Tags #dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Your probability calculation at line '' double ff = 1.0/sz(v[y]); '' is wrong. Here for a node not leaf, you are including its parent also, which reduces the probability of its children. Just change it to the probability of its children and your solution will be accepted. Check : 57641710 Sample test: 6 1 2 1 3 3 4 2 5 2 6