SAT2020's blog

By SAT2020, history, 20 months ago, In English

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:

  1. Binary search for the optimal weight
  2. Verify potential weights by creating a graph of only nodes with that weight or less...
  3. 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.com/contest/1679/submission/166858130

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

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.