Hey Everyone,
I'm trying to solve problem 1679D, but I'm getting TLE despite using the strategy suggested by the editorial. The basic idea behind this problem is that you have a graph and each node has a weight. You need to find the path with the minimum-maximum weight, where the path must be at least k vertices. The strategy suggested by the editorial is to:
- Binary search for the optimal weight
- Verify potential weights by creating a graph of only nodes with that weight or less...
- Perform a topological sort on that graph, use that sort to calculate the maximum path, and return true if that maximum path exceeds the minimum vertices k.
Unfortunately, when I implemented this strategy, I got TLE. Any help in understanding this problem would be greatly appreciated!
Code: https://codeforces.net/contest/1679/submission/166858130
I have found the issue! To anyone reading this in the future: the complexity of inserting a value in the front of a vector is O(n). By contrast, the complexity of pushing back to a vector is just O(1). Therefore, the best way to write a topological sort is to push everything to the back of the vector and then reverse it afterward.