# POI Task Rally (88pts - TLE)

Jul 19th, 2022
805
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. 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.
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. }