TLE on Codeforces Round #791, Problem D (1679D)

Revision en1, by SAT2020, 2022-08-04 01:37:08

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.net/contest/1679/submission/166858130

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SAT2020 2022-08-04 01:37:08 911 Initial revision (published)