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.

Before contest

TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)

09:31:44

Register now »

TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)

09:31:44

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | adamant | 163 |

6 | maroonrk | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 155 |

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.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2023 08:03:18 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

__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.

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 ?

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

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