time complexity of TREE-GCD

for dis two codes : https://www.codechef.com/viewsolution/15151327 and https://www.codechef.com/viewsolution/15105382 i thnk time complexity is same…bt why nly d first code is getting accepted and d second one TLE ??
if im wrong in calculating time complexity pls correct !!
thanks in advance : )

It seems you are pushing nodes into queue repeatedly…in second code you are marking vis[node] and no where i can see something like !vis[node]…probably this could be reason.

I forgot to comment it out !!

If not because of what @srikanth_16 has said, I think it is probably because of the use of long long instead of int and the time complexity must be very strict here which is why the 2nd code didn’t pass.

Try using Int instead of long long.

but in both d codes bfs is applied to every node and also in both codes tree is considered as directed one and hence der is no need to use a boolean array to check whether it is visited or not ri8 ??

1 Like

i have tried jst now…even dat didnt work !!

One thing is common to both these solutions, you are assuming the edge is always directed from parent to child, but it is not mentioned anywhere in the question. It seems that test cases for this problem are that way, but one should not assume that.

No, because the bfs runs until the queue is empty

yeah…true (:

can u say me d correct approach to solve dis question for 30 points using bfs/dfs ?? @meooow

Found it. You’re not clearing the tree itself, i.e the adjacency lists.


so…if i clear( tree[i].clear() ) after every bfs…will it get accepted ??

For each vertex, yes. You should get 30 points after that.

got WA ,code : https://www.codechef.com/viewsolution/15163992

That’s probably because you are doing tree[i].clear() in the main loop itself.
It’s better to cycle over the vertices and clear each list at the end of each test case.
EDIT: Yes it works: link :slight_smile:

AC @meooow…thanks bro !!