Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Doubt in the problem Water Tree [Codeforces Round 200 Div 1 D]

Revision en4, by kshitij_07, 2019-06-29 09:28:51

I tried doing this problem, but am getting WA on bigger test cases. I'll explain my code and what I did.

(1) I converted the tree into an array according to the start and end time of a node's visit.

(2) addT (corresponding add_lazy) stores the range which has been watered (If watering a node, I update all the nodes in its subtree by update over its time_in and time_out). While watering a node, I remove(unset) all the nodes in its subtree which could probably have been emptied earlier. delT (corresponding del_lazy) stores the node that has been emptied (It just stores the nodes and nothing else about its ancestors)

(3) When querying, I check if a node is watered (if query1 on addT on its start time returns 1), if it is not, then output 0, else if it is, then I check if any node in its subtree is emptied ( query2 on time_in[node] to time_out[node]), if any is, then output 0 else 1.

Can someone please point out any fault in the logic or implementation. Please comment if you need me to explain anything more about the code.

Thanks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English kshitij_07 2019-06-29 09:28:51 83 Tiny change: ' emptied (**query2**' -> ' emptied ( **query2**' (published)
en3 English kshitij_07 2019-06-29 09:26:53 73
en2 English kshitij_07 2019-06-29 09:25:27 822
en1 English kshitij_07 2019-06-29 09:19:50 281 Initial revision (saved to drafts)