strglntoexist's blog

Help!!!Getting TLE on Test 2 of CF 731 (Division 3) G
By strglntoexist, history, 3 years ago, In English

Here is the link of the problem: 1547G - Сколько путей?

Here is the code which is getting TLE:

Code

I am using dfs to find cycle and the number of paths from 1 to the current vertex. This is dfs1 function. Then I am using these information to get the answer in dfs2 function. The cycle function is for getting the vertex which form the cycle. The cycle array marks the nodes of the cycle. The arr array is to count the number of paths or how many times each vertex is visited and the ans array is for storing the answer. The par array stores the parent of each vertex which is used to get the cycle in cycle function. The vis arrays are for detecting a cycle. But i am getting TLE. I have used dfs 2 times . As dfs is O(V+E) it should pass. Can anybody explain why I am getting TLE? Here is the submission: 122422271

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your code goes into TLE for the following test case :

1
6 6
1 5
3 6
5 1
5 3
6 3
6 5
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can see the tutorial.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I know about the tutorial but I could not find the bug in my code. Thanks for replying anyways

    → Reply