求助玄关88pts 码风良好

开O2: TLE on #6 不开O2:RE on #6

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int maxm=2e6+10;
int head[maxn],bel[maxn],sz[maxn],dp[maxn],g[maxn],low[maxn],dfn[maxn];
int HEAD[maxn];
struct edge{
    int to,next;
}edge[maxm],EDGE[maxn];
int n,m,modp;
stack<int> stk;
vector<int> scc[maxn];
bool instack[maxn],vis[maxn];
int tot=0,cnt=0,fcnt=0,CNT=0;
void init(){
    for(int i=1;i<=n;i++) head[i]=-1;
}
void INIT(){
    for(int i=1;i<=n;i++) HEAD[i]=-1;
}
void add_edge(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void ADD_EDGE(int u,int v){
    EDGE[CNT].to=v;
    EDGE[CNT].next=HEAD[u];
    HEAD[u]=CNT++;
}
void tarjan(int u){
    low[u]=dfn[u]=++tot;
    instack[u]=true;
    stk.push(u);
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++fcnt;
        while(true){
            int x=stk.top();
            scc[fcnt].push_back(x);
            bel[x]=fcnt;
            sz[fcnt]++;
            stk.pop();
            instack[x]=false;
            if(x==u) break;
        }
    }
}
void rebuild(){
    for(int k=1;k<=fcnt;k++){
        dp[k]=sz[k];
        g[k]=1;
        for(auto u:scc[k]){
            for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].to;
                if(!vis[bel[v]]&&bel[v]!=bel[u]){
                    vis[bel[v]]=true;
                    ADD_EDGE(bel[u],bel[v]);
                }
            }
        }
        for(auto u:scc[k]){
            for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].to;
                vis[bel[v]]=false;
            }
        }
    }
}
void dfs(){
    for(int x=fcnt;x>=1;x--){
        for(int i=HEAD[x];i!=-1;i=EDGE[i].next){
            int v=EDGE[i].to;
            if(dp[v]<dp[x]+sz[v]){
                dp[v]=dp[x]+sz[v];
                g[v]=g[x];
            }
            else if(dp[v]==dp[x]+sz[v]){
                g[v]=(g[v]+g[x])%modp;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>modp;
    init();
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add_edge(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    INIT();
    rebuild();
    dfs();
    int ans=0;
    int tmp=0;
    for(int i=1;i<=fcnt;i++){
        if(dp[i]>ans){
            ans=dp[i];
            tmp=g[i];
        }
        else if(dp[i]==ans){
            tmp=(tmp+g[i])%modp;
        }
    }
    cout<<ans<<endl<<tmp;
}