POI Task Rally (88pts - TLE)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX_N = 5e5, MAX_M = 1e6;
int inverseV[1+MAX_N];
int pathLeft[1+MAX_N], pathRight[1+MAX_N]; // max path length

const int MAX_RANGES_SIZE = 2*MAX_N + MAX_M;
pair<pair<int, int>, int> ranges[MAX_RANGES_SIZE]; /* l, r, pathSize
    removing any node in the range [l, r) (on sorted indices)
    leaves a path of size pathSize */
bool endedRange[MAX_RANGES_SIZE];

// Topological sort
vector<vector<int>> g;
bool seen[1+MAX_N];
vector<int> v;
void dfs(int node) {
    if (seen[node]) return;
    seen[node] = true;
    for (int x : g[node]) dfs(x);
    v.push_back(node);
}
void topoSort(int n) {
    for (int i = 1; i <= n; ++i) {
        if (!seen[i]) dfs(i);
    }
    reverse(v.begin(), v.end());
}

int main() {
    int n, m; scanf("%d %d", &n, &m);
    g.resize(1+n);
    for (int i = 0; i < m; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        g[x].push_back(y);
    }
    topoSort(n);

    for (int i = 0; i < n; ++i) inverseV[v[i]] = i;

    // Precalculate path sizes
    for (int i = 0; i < n; ++i) {
        int x = v[i];
        for (int y : g[x]) pathLeft[y] = max(pathLeft[y], pathLeft[x]+1);
    }
    for (int i = n-1; i >= 0; --i) {
        int x = v[i];
        for (int y : g[x]) pathRight[x] = max(pathRight[x], pathRight[y]+1);
    }

    int rangesSize = 0;
    for (int i = 0; i < n; ++i) {
        int x = v[i];
        ranges[rangesSize++] = {{i+1, n}, pathLeft[x]}; // take as left
        ranges[rangesSize++] = {{0, i}, pathRight[x]}; // take as right
        // take as left with its child as right
        for (int y : g[x]) ranges[rangesSize++] = {{i+1, inverseV[y]}, pathLeft[x]+1+pathRight[y]};
    }
    sort(ranges, ranges+rangesSize);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ends;
    priority_queue<pair<int, int>> pathSizes;
    pathSizes.emplace(0, -1);
    int nextRange = 0;
    int ansID = -1, ansMaxPath = n+1;
    for (int i = 0; i < n; ++i) {
        // start necessary ranges
        while (nextRange < rangesSize && ranges[nextRange].first.first == i) {
            pathSizes.emplace(ranges[nextRange].second, nextRange);
            ends.emplace(ranges[nextRange].first.second, nextRange);
            nextRange++;
        }

        // end necessary ranges
        while (!ends.empty() && ends.top().first == i) {
            endedRange[ends.top().second] = true;
            ends.pop();
        }

        // get largest answer
        while (!pathSizes.empty() && endedRange[pathSizes.top().second]) pathSizes.pop();
        int maxPath = pathSizes.top().first;
        if (maxPath < ansMaxPath) {
            ansMaxPath = maxPath;
            ansID = v[i];
        }
    }
    printf("%d %d\n", ansID, ansMaxPath);
    return 0;
}