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?
Auto comment: topic has been updated by ameyanator (previous revision, new revision, compare).
Urm anyone please?!
Either adding
cout.tie(0)or usingscanf/printfmay work :).UPD: No, it's not any of them, I tried.
Yeh I had tried these and still TLE.
Your solution's complexity seems to be O(V3).
Yes you are right and that is why I'm getting a TLE. :(.
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.