### ameyanator's blog

By ameyanator, history, 11 months ago, ,

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?

•
• +5
•

 » 11 months ago, # |   0 Auto comment: topic has been updated by ameyanator (previous revision, new revision, compare).
 » 11 months ago, # |   0 Urm anyone please?!
 » 11 months ago, # | ← Rev. 2 →   0 Either adding cout.tie(0) or using scanf/printfmay work :).UPD: No, it's not any of them, I tried.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +1 Yeh I had tried these and still TLE.
 » 11 months ago, # |   0 Your solution's complexity seems to be O(V3). in worst case
•  » » 11 months ago, # ^ |   0 Yes you are right and that is why I'm getting a TLE. :(.
 » 11 months ago, # |   0 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.