Jul 19th, 2022
942
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
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. }