Блог пользователя rahulpadhy

Автор rahulpadhy, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.