RT

luogu非O2评测记录

luoguO2评测记录

下面是代码，求大佬看看能否改进QwQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e5+5,M=1e6+5;
int a,MOD,dfn[N],low[N],st[N],col[N],dep,num,top,siz[N],dp[N],fr[M],to[M],pos[M],deg[N],dis[N],ans;
int q[N],h,t,alans;
vector<int> g[N],ng[N];
void tarjan(int now)
{
    int i;
    dfn[now]=++dep;
    low[now]=dep;
    st[++top]=now;
    for(i=0;i<g[now].size();i++)
    {
        int tmp=g[now][i];
        if(!dfn[tmp])
        {
            tarjan(tmp);
            low[now]=min(low[now],low[tmp]);
        }
        else if(!col[tmp]) low[now]=min(low[now],low[tmp]);
    }
    if(dfn[now]==low[now])
    {
        col[now]=++num;
        siz[num]++;
        while(st[top]!=now)
        {
            col[st[top--]]=num;
            siz[num]++;
        }
        top--;
    }
}
bool cmp(int x,int y)
{
    if(fr[x]!=fr[y]) return fr[x]<fr[y];
    return to[x]<to[y];
}
int main()
{
    int b,c,d,i,j;
    scanf("%d%d%d",&a,&b,&MOD);
    for(i=0;i<b;i++)
    {
        scanf("%d%d",&c,&d);
        fr[i]=c,to[i]=d;
        g[c].push_back(d);
    }
    //tarjan
    for(i=1;i<=a;i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    //去缩点后重边
    for(i=0;i<b;i++)
    {
        pos[i]=i;
        fr[i]=col[fr[i]];
        to[i]=col[to[i]];
    }
    sort(pos,pos+b,cmp);
    //统计入度
    for(i=0;i<b;i++)
    {
        if(fr[pos[i]]==to[pos[i]]||(fr[pos[i]]==fr[pos[i-1]]&&to[pos[i]]==to[pos[i-1]])) continue;
        ng[fr[pos[i]]].push_back(to[pos[i]]);
        deg[to[pos[i]]]++;
    }
    //拓扑排序初始化 
    for(i=1;i<=num;i++)
    {
        if(!deg[i])
        {
            q[t++]=i;
            dis[i]=siz[i];
            dp[i]=1;
            if(dis[ans]<dis[i]) ans=i;
        }
    }
    //拓扑 
    while(h<t)
    {
        int tmp=q[h++];
        for(i=0;i<ng[tmp].size();i++)
        {
            int taim=ng[tmp][i];
            if(!--deg[taim]) q[t++]=taim;
            if(dis[taim]<dis[tmp]+siz[taim])
            {
                dis[taim]=dis[tmp]+siz[taim];
                dp[taim]=0;
                if(dis[ans]<dis[taim]) ans=taim;
            }
            if(dis[taim]==dis[tmp]+siz[taim]) dp[taim]=(dp[tmp]+dp[taim])%MOD;
        }
    }
    for(i=1;i<=num;i++) if(dis[i]==dis[ans]) alans=(alans+dp[i])%MOD;
    printf("%d\n%d",dis[ans],alans);
    return 0;
}