kshitij_07's blog

By kshitij_07, history, 5 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it