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

Правка en4, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский kshitij_07 2019-06-29 09:28:51 83 Tiny change: ' emptied (**query2**' -> ' emptied ( **query2**' (published)
en3 Английский kshitij_07 2019-06-29 09:26:53 73
en2 Английский kshitij_07 2019-06-29 09:25:27 822
en1 Английский kshitij_07 2019-06-29 09:19:50 281 Initial revision (saved to drafts)