Advertisement
erek1e

POI Task Rally

Jul 19th, 2022
942
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.51 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.  
  17. // Topological sort
  18. vector<vector<int>> g;
  19. bool seen[1+MAX_N];
  20. vector<int> v;
  21. void dfs(int node) {
  22.     if (seen[node]) return;
  23.     seen[node] = true;
  24.     for (int x : g[node]) dfs(x);
  25.     v.push_back(node);
  26. }
  27. void topoSort(int n) {
  28.     for (int i = 1; i <= n; ++i) {
  29.         if (!seen[i]) dfs(i);
  30.     }
  31.     reverse(v.begin(), v.end());
  32. }
  33.  
  34. int main() {
  35.     int n, m; scanf("%d %d", &n, &m);
  36.     g.resize(1+n);
  37.     for (int i = 0; i < m; ++i) {
  38.         int x, y; scanf("%d %d", &x, &y);
  39.         g[x].push_back(y);
  40.     }
  41.     topoSort(n);
  42.    
  43.     for (int i = 0; i < n; ++i) inverseV[v[i]] = i;
  44.  
  45.     // Precalculate path sizes
  46.     for (int i = 0; i < n; ++i) {
  47.         int x = v[i];
  48.         for (int y : g[x]) pathLeft[y] = max(pathLeft[y], pathLeft[x]+1);
  49.     }
  50.     for (int i = n-1; i >= 0; --i) {
  51.         int x = v[i];
  52.         for (int y : g[x]) pathRight[x] = max(pathRight[x], pathRight[y]+1);
  53.     }
  54.  
  55.     int rangesSize = 0;
  56.     for (int i = 0; i < n; ++i) {
  57.         int x = v[i];
  58.         ranges[rangesSize++] = {{i+1, n}, pathLeft[x]}; // take as left
  59.         ranges[rangesSize++] = {{0, i}, pathRight[x]}; // take as right
  60.         // take as left with its child as right
  61.         for (int y : g[x]) ranges[rangesSize++] = {{i+1, inverseV[y]}, pathLeft[x]+1+pathRight[y]};
  62.     }
  63.     sort(ranges, ranges+rangesSize);
  64.  
  65.     priority_queue<pair<int, int>> pathSizes;
  66.     pathSizes.emplace(0, n);
  67.     int nextRange = 0;
  68.     int ansID = -1, ansMaxPath = n+1;
  69.     for (int i = 0; i < n; ++i) {
  70.         // start necessary ranges
  71.         while (nextRange < rangesSize && ranges[nextRange].first.first == i) {
  72.             pathSizes.emplace(ranges[nextRange].second, ranges[nextRange].first.second);
  73.             nextRange++;
  74.         }
  75.  
  76.         // get largest answer
  77.         while (!pathSizes.empty() && pathSizes.top().second <= i) pathSizes.pop();
  78.         int maxPath = pathSizes.top().first;
  79.         if (maxPath < ansMaxPath) {
  80.             ansMaxPath = maxPath;
  81.             ansID = v[i];
  82.         }
  83.     }
  84.     printf("%d %d\n", ansID, ansMaxPath);
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement