POPTUNNL: Calling for help!

Question Link: https://www.codechef.com/problems/POPTUNNL
My Solution: https://www.codechef.com/viewsolution/29218557
Why is it getting TLE!. I have used BFS approach.

1 Like

Found the bug finally!
Take for example, graph with edges between 1\rarr 2, 2\rarr 3 and 1\rarr 3.
Initially, your queue contains \{1,0\}.
After processing node 1, your queue will contain values \{2,1\}, \{3,1\}. At this point, only Visited[1] = 1. Now, you process the next element in the queue.
This is where the bug lies. Notice that, after processing of this node, pair \{3,2\} gets added into the queue which is the cause for duplicates in you queue(\{3,1\} and \{3,2\}). This is what slows down your code and gives a TLE.
Hope it helped!

1 Like

The fix for this is setting visited[i] = 1 for every i, with reference to your code. Corrected code is attached below
https://www.codechef.com/viewsolution/29220791

1 Like

PLEASE HELP ME IN UNDERSTANDING HOW IS MY APPROACH WRONG .
https://www.codechef.com/viewsolution/29187045