for dis two codes : CodeChef: Practical coding for everyone and CodeChef: Practical coding for everyone 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.
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.
Found it. You’re not clearing the tree itself, i.e the adjacency lists.
3 Likes
I forgot to comment it out !!
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 (:
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.
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 