rahulpadhy's blog

ADDAP spoj
By rahulpadhy, history, 9 years ago, In English

I am stuck in this SPOJ question. Can anyone please point out as to where I am going wrong ? I am not even getting the sample test cases correct..

Here's the link to the question :

http://www.spoj.com/problems/ADDAP/

And here's my solution for it. I am using BFS to detect the level of the nodes(I am pushing -1 into the queue after completion of each level & -1 here detects the completion of a level), but unfortunately not getting the correct answer.

http://pastebin.com/WnfkQXXH

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

Comments Comments (1)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You seem to be assuming that all the edges in the input are directed from parent to child.

Even if you fix that your complexity is O(N^2), so it won't pass.

Note that if you have updates (u, x, y) and (u, x', y') you can combine them into (u, x + x', y + y'). So you can group the updates for one node into a single update.

Also note that applying (u, x, y) means adding x to solution[u], and then applying (c, x + y, y) for all children c of u.

Using those two (though not completely naively) you should be able to solve the problem in a single dfs.

→ Reply