shreyas_171's blog

Codeforces #756 Div-3 problem D doubt
By shreyas_171, history, 3 years ago, In English

Can anyone tell me why I'm getting WA on Test case 1 ?? Since it was Constructive Algo, I'm not able to figure out what's wrong in the logic .

Solution Link

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

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

~~~~~ for (ll i = 2; i <= n; i++) {

f[dist[i]] = rand ;
    rand -= -1;

}~~~~~

This in your code is wrong. The rand variable is the distance from the root in your case and not from the parent of the vertex. Note we need to return the distance of a vertex from its parent in answer and not its root. You need a second array inn which you can store the sum the parent of the vertex and then the answer for that vertex will be f[dist[i]] = rand-totaldistancetill[parentofvertex/dist[i]]; where totaldistancetill is an array which stores the total distance from root to the point which we want that is equal to rand in your case. 136907232 You can check this if you want.

I hope i have made it a little clear then before, if not i am sorry for not being able to help properly.

Note: you might also have to check in the dist array that a vertex is not called before its parent else the solution will not be there.

→ Reply