2 TCs giving TLE in Mike and Or tree!

#1

my sol : https://ide.codingblocks.com/s/292770

can u pls tell me why my code is giving TLE and how can i further optimize my soln ??

according to me the code shouldn’t give TLE !!

#2

@saarthakseth hey try this approach it is more efficient:
The problem can be solved in different ways. The most easy idea is sqrt-optimization. Split all queries into sqrt(n) blocks. Each block we will process separately. Before processing each block, we should calculate minimum distances from every node to the closest node with value 1 using bfs. To answer the query we should update this value by shortest distances to nodes with value 1 in current block.

The solution becomes simple. Every sqrt(n) queries we make simple bfs and for every node v WE calculate value d[v] — the shortest distance to some node with value 1 from node v. Then to answer the query of type 2 you should calculate min(d[v], dist(v, u)), where u — every node with value 1, which is updated in current block of length sqrt(n). dist(v,u) can be calculated by using sparse table for LCA,
dist(v,u) = level_v + level_u - 2*level_lca_vu

Time Complexity : O(N * sqrt(N) * log(N))

#3

ok, i’ll try this approach

#4

but can u pls tell why is soln giving TLE ? I think my soln too has the same time complexity

#5

can u pls share the implementation ? I am not able to implement your approach :slight_smile:

#6

@saarthakseth hey here is code for your reference:

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.