My Approach
i created an array of length n+1 size(i am ignoring index 0)which holds -1 value initially. My approach was using DFS/BFS and doing XOR Operation … if vertex in intially unvisited than store xor output…if vertex is already visited than Check whether xor output and stored value do not conflict with each other… if they then answer will be no…
according to concept time complexity of BFS/DFS is O(V+E) and in problem its given that
Sum of each of N, Q over all test cases doesn’t exceed 106
so why my last is giving TLE… Plz help
my Code Link
Thats weird, because that test case took 0.18 sec for me while the one you passed seemed bulky to me (took good 1.35 seconds !!)
You can look at my solution here , even I used DFS. See if you can figure it out, meanwhile I am looking at your code 
1 Like
there may be any case in 4th one where some infinite loop is running…
Yes, even I have this notion in mind. But I feel trying to figure out the case will take lot of effort, considering that its a large TC, and that you passed almost all TCs.
i was thinking over it from past 2 days what can be the issue
Its not an infinite loop. Using M.C.A , I saw that your loop executes ~ {10}^{4} instructions in 3.41 seconds in that case.This has got to do something with algorithm. Something is taking more time than you think. Perhaps something which you thought is O(1) is actually O(N) (accessing element, deleting element, adding element are possible things we need to re-look)
1 Like
sorry, what do u mean by M.C.A
Lol, sorry, you can disregard that. Its a method I use for debugging, to check presence of infinite loop.
LinkedList is using O(n) for accessing the ith element of the list, so l.get® inyour inner loop takes O(n). The degree of a vertex can be up to O(n) so the inner loop can take O(n^2) which times out. You have to either iterate over the linked list directly or use a datatype with O(1) access (like ArrayList).
6 Likes
yes it worked… thanku bro
@vijju as u said, accessing elements in linkedlist by get® was taking O(N) and i was thinking its O(1). lost chance to get full 100 points due to this silly mistake in sept17…
The most reliable things give the cruelest deceptions…
1 Like