praveenojha33's blog

Unable to understand reason for MLE ?
By praveenojha33, history, 5 years ago, In English

I was solving problem https://mirror.codeforces.com/problemset/problem/601/A in which I was using simple BFS but I took MLE on test 57, but when I changed the way of marking visited node slightly it got accepted. Can anyone help me to understand the reason for this ?

This approach was Accepted. https://mirror.codeforces.com/contest/601/submission/55706140

This approach gave MLE https://mirror.codeforces.com/problemset/submission/601/55703452

The only difference is in the way how I mark visited node.

Thank You !!

Tags bfs, mle
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

You marked visited node when you already pop it, but in this moment there may be several more in queue(in additional you dont check if you already pop this node) and your code pop this node again. But in Accepted submission you marked node after first pushing and there can be only one node in queue

You may add if(vis[u.F]) continue; when poping https://mirror.codeforces.com/problemset/submission/601/55707981

→ Reply