take_me_back's blog

[Help] Memory limit exceeded
By take_me_back, history, 5 years ago, In English

Hi guys, Why my implementation to problem https://mirror.codeforces.com/contest/1278/problem/D gives MLE, First I though it is because of recursive DFS. But even after changing DFS to iterative it is still giving MLE. Can anyone please help me with it. My solution links

https://pastebin.com/T5eqyXYS (Recursive)

https://pastebin.com/KczMMcud (Iterative)

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

»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

It might be because of too large amount of edges in graph. Tree with n vertexes has n-1 edges, so you can check that excession easily.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In the worst case, you might end up inserting $$$O(n^2)$$$ edges. So, one idea is to terminate immediately once you find that the no. of edges have become $$$\ge n$$$, since a tree has only $$$(n-1)$$$ edges.

→ Reply