ameyanator's blog

By ameyanator, history, 6 months 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 months 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).

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

Urm anyone please?!

»
6 months 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.

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

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

in worst case

  • »
    »
    6 months 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. :(.

»
6 months 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.