i_love_emilia_clarke's blog

Problem — New Year Tree
By i_love_emilia_clarke, history, 8 years ago, In English

Hi there, i am stuck at the problem Codeforces Eductional Round 6 I read the tutorial and tried implementing the same, here is my Code. I think the problem is with the lazy propagation, please try to find the mistake.

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

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

__builtin_popcount(mask) works with ints, you should use __builtin_popcountll(mask) instead.

Also, I think that if for some vertex v its parent has a greater label, then your segment tree initialization isn't correct. But I'm not sure.

And an observation not so important: You don't need the "complete" Euler tour, you could add vertices only at discovery time.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi pulgares, thanks for the __builtin_popcountll(mask) thing, would have stuck at this forever. I checked the initialization(2 times), it looks fine to me, maybe you want pass me a small test cases

    I fail to catch this completely(but this fact looks quite interesting), i agree that we don't need to store euler tour for filling up starting and ending index of each vertex in euler tour, but we still need it to query over a subsegment which represent the subtree of a given vertex, or are you trying to imply that there is more cleaner/shorter/swaggy way to do it(please say yes) ?

    if we add vertices only at the discovery time, then how would we know the range of updation, obviously the node in the subtree of a vertex would get discovered after it, but so will other node which are not, so how will we decide till which index in th euler tour array we have to update the values ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
      3 1
1 2 3
1 3
3 2
2 1

      there, your code gives 2 as the answer and should be 3.

      "please say yes" haha sorry :p What I suggest is pretty much the same, every subtree is a subsegment of the array. In the dfs you add the vertex only at discovery time and the segment of its subtree is from there to the last vertex of its subtree, I think you can delete these two lines

      E[pos] = v 	;
pos ++		;

      from your dfs loop and it will work as I suggest.

      → Reply