(POI) XXI OI Round II - day 2 Task Rally

https://szkopul.edu.pl/problemset/problem/BnzEADCfeJFjjev1Y9iHQANg/site/?key=statement

超級無敵精湛的一題XDD。

要不是有set還真的可以壓到O(N+M) XDD。

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

const int N = 500006;

vector<int> oriG[N];
vector<int> preG[N];
vector<int> sufG[N];

int mp[N];

int predp[N],predpmx[N];
int sufdp[N],sufdpmx[N];
int deg[N];

vector< pair<int,int> > in_event[N],out_event[N];

int main ()
{
    vector< pair<int,int> > edges;
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;m>=i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        oriG[x].push_back(y);
        deg[y]++;
        edges.push_back(make_pair(x,y));
    }
    queue<int> que;
    for (int i=1;n>=i;i++)
    {
        if (!deg[i])
        {
            que.push(i);
        }
    }
    int id=0;
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        mp[t] = ++id;
        for(int j:oriG[t])
        {
            deg[j]--;
            if (!deg[j])
            {
                que.push(j);
            }
        }
    }
    for (pair<int,int> &p:edges)
    {
        p.first = mp[p.first];
        p.second = mp[p.second];
        preG[p.second].push_back(p.first);
        sufG[p.first].push_back(p.second);
    }
    for (int i=1;n>=i;i++)
    {
        predp[i] = 0;
        for (int j:preG[i])
        {
            predp[i] = max(predp[i],predp[j] + 1);
        }
        predpmx[i] = max(predpmx[i-1],predp[i]);
    }
    for (int i=n;i>=1;i--)
    {
        sufdp[i] = 0;
        for (int j:sufG[i])
        {
            sufdp[i] = max(sufdp[i],sufdp[j] + 1);
        }
        sufdpmx[i] = max(sufdpmx[i+1],sufdp[i]);
    }
    for (pair<int,int> p:edges)
    {
        if (p.second - p.first > 1)
        {
            in_event[p.first+1].push_back(p);
            out_event[p.second].push_back(p);
        }
    }
    int mx=(1<<30),ans=0;
    multiset<int> st;
    for (int i=1;n>=i;i++)
    {
        int tmpmx = max(predpmx[i-1],sufdpmx[i+1]);
        for (pair<int,int> p:in_event[i])
        {
            st.insert(predp[p.first] + sufdp[p.second] + 1);
        }
        for (pair<int,int> p:out_event[i])
        {
            st.erase(st.find(predp[p.first]+sufdp[p.second]+1));
        }
        if (!st.empty())
        {
            tmpmx = max(tmpmx,*(--st.end()));
        }
        if (tmpmx < mx)
        {
            mx = tmpmx;
            ans = i;
        }
    }
    for (int i=1;n>=i;i++)
    {
        if (mp[i] == ans)
        {
            ans = i;
            break;
        }
    }
    printf("%d %d\n",ans,mx);
}