Advertisement
erek1e

POI Task Rally (88pts - TLE)

Jul 19th, 2022
691
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX_N = 5e5, MAX_M = 1e6;
  9. int inverseV[1+MAX_N];
  10. int pathLeft[1+MAX_N], pathRight[1+MAX_N]; // max path length
  11.  
  12. const int MAX_RANGES_SIZE = 2*MAX_N + MAX_M;
  13. pair<pair<int, int>, int> ranges[MAX_RANGES_SIZE]; /* l, r, pathSize
  14.     removing any node in the range [l, r) (on sorted indices)
  15.     leaves a path of size pathSize */
  16. bool endedRange[MAX_RANGES_SIZE];
  17.  
  18. // Topological sort
  19. vector<vector<int>> g;
  20. bool seen[1+MAX_N];
  21. vector<int> v;
  22. void dfs(int node) {
  23.     if (seen[node]) return;
  24.     seen[node] = true;
  25.     for (int x : g[node]) dfs(x);
  26.     v.push_back(node);
  27. }
  28. void topoSort(int n) {
  29.     for (int i = 1; i <= n; ++i) {
  30.         if (!seen[i]) dfs(i);
  31.     }
  32.     reverse(v.begin(), v.end());
  33. }
  34.  
  35. int main() {
  36.     int n, m; scanf("%d %d", &n, &m);
  37.     g.resize(1+n);
  38.     for (int i = 0; i < m; ++i) {
  39.         int x, y; scanf("%d %d", &x, &y);
  40.         g[x].push_back(y);
  41.     }
  42.     topoSort(n);
  43.    
  44.     for (int i = 0; i < n; ++i) inverseV[v[i]] = i;
  45.  
  46.     // Precalculate path sizes
  47.     for (int i = 0; i < n; ++i) {
  48.         int x = v[i];
  49.         for (int y : g[x]) pathLeft[y] = max(pathLeft[y], pathLeft[x]+1);
  50.     }
  51.     for (int i = n-1; i >= 0; --i) {
  52.         int x = v[i];
  53.         for (int y : g[x]) pathRight[x] = max(pathRight[x], pathRight[y]+1);
  54.     }
  55.  
  56.     int rangesSize = 0;
  57.     for (int i = 0; i < n; ++i) {
  58.         int x = v[i];
  59.         ranges[rangesSize++] = {{i+1, n}, pathLeft[x]}; // take as left
  60.         ranges[rangesSize++] = {{0, i}, pathRight[x]}; // take as right
  61.         // take as left with its child as right
  62.         for (int y : g[x]) ranges[rangesSize++] = {{i+1, inverseV[y]}, pathLeft[x]+1+pathRight[y]};
  63.     }
  64.     sort(ranges, ranges+rangesSize);
  65.  
  66.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ends;
  67.     priority_queue<pair<int, int>> pathSizes;
  68.     pathSizes.emplace(0, -1);
  69.     int nextRange = 0;
  70.     int ansID = -1, ansMaxPath = n+1;
  71.     for (int i = 0; i < n; ++i) {
  72.         // start necessary ranges
  73.         while (nextRange < rangesSize && ranges[nextRange].first.first == i) {
  74.             pathSizes.emplace(ranges[nextRange].second, nextRange);
  75.             ends.emplace(ranges[nextRange].first.second, nextRange);
  76.             nextRange++;
  77.         }
  78.  
  79.         // end necessary ranges
  80.         while (!ends.empty() && ends.top().first == i) {
  81.             endedRange[ends.top().second] = true;
  82.             ends.pop();
  83.         }
  84.  
  85.         // get largest answer
  86.         while (!pathSizes.empty() && endedRange[pathSizes.top().second]) pathSizes.pop();
  87.         int maxPath = pathSizes.top().first;
  88.         if (maxPath < ansMaxPath) {
  89.             ansMaxPath = maxPath;
  90.             ansID = v[i];
  91.         }
  92.     }
  93.     printf("%d %d\n", ansID, ansMaxPath);
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement