ameyanator's blog

Help needed to solve SPOJ question ADACYCLE. (Getting TLE)
By ameyanator, history, 6 years ago, In English

I've been trying to solve this question, but I keep on getting a TLE. At first I had an O(V*(E+V)) approach (link). Then I optimized my code so that I store the results of other nodes while calculating the answer of some node. (link). I'm still getting an TLE.

Can anyone please suggest another optimization/approach for this question so that I can get an AC?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ameyanator (previous revision, new revision, compare).

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

Urm anyone please?!

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

Either adding cout.tie(0) or using scanf/printfmay work :).

UPD: No, it's not any of them, I tried.

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

Your solution's complexity seems to be O(V3).

in worst case

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

    Yes you are right and that is why I'm getting a TLE. :(.

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

Update Solved the question. All it required was an optimization — Inside our bfs we need to consider only those nodes that the current node stems out to. We can preprocess this or use adjacency list representation.

→ Reply