小Y的炮

【存代码】

#include<bits/stdc++.h>

#define N 1000001

#define MAXN 100001

using namespace std;

int n,m,Mo,h1,top,h,t,ans;

int ru[N],x[N],y[N],w1[N],to[N];

int p[MAXN],w2[MAXN],x2[MAXN];

int es[MAXN],xy[MAXN],f[MAXN];

int df[MAXN],wu[MAXN],st[MAXN],cn[MAXN],rst[MAXN];

int h2,cnt,u,ex;

void Build(int x,int y){

    h1++;

    w1[h1]=p[x];

    p[x]=h1;

    to[h1]=y;

}

bool cmp(int a,int b){

    if(x[a]!=x[b])

        return x[a]<x[b];

    else

        return y[a]<y[b];

}

void tar(int xx){

    df[xx]=wu[xx]=++ex;

    st[++top]=xx;

    for(int i=p[xx];i;i=w1[i]){

        if(!df[to[i]]){

            tar(to[i]);

            wu[xx]=min(wu[xx],wu[to[i]]);

        }

        else

            if(!cn[to[i]])

                wu[xx]=min(wu[xx],df[to[i]]);

    }

    if(wu[xx]==df[xx]){

        cn[xx]=++cnt;xy[cnt]++;

        while(st[top]!=xx){

            cn[st[top]]=cnt;

            top--;

            xy[cnt]++;

        }

        top--;

    }

}

int main(){

    scanf("%d%d%d",&n,&m,&Mo);

    for (int i=;i<=m;i++){

        scanf("%d%d",&x[i],&y[i]);

        Build(x[i],y[i]);

    }

    for (int i=;i<=n;i++)

        if (!df[i])

            tar(i);

    for (int i=;i<=m;i++){

        ru[i]=i;

        x[i]=cn[x[i]];

        y[i]=cn[y[i]];

    }

    sort(ru+,ru++m,cmp);

    h1=;

    memset(p,,sizeof(p));

    for (int i=;i<=m;i++)

        if((x[ru[i]]!=y[ru[i]])&&(x[ru[i]]!=x[ru[i-]]||y[ru[i]]!=y[ru[i-]])){

        //if (x[ru[i]]!=y[ru[i]])

            //if (x[ru[i]]!=x[ru[i-1]]||y[ru[i]]!=y[ru[i-1]]){

                w2[y[ru[i]]]++;

                Build(x[ru[i]],y[ru[i]]);

            }

    for (int i=;i<=cnt;i++)

        if (!w2[i]){

            //t++;

            rst[++t]=i;

            f[i]=xy[i];

            x2[i]=;

            if (f[ans]<f[i])

                ans=i;

        }

    while (h<t){

        h++;

        u=rst[h];

        for (int k=p[u];k;k=w1[k]){

            w2[to[k]]--;

            //f[to[k]=min(f[to[k]],f[u]+xy[to[k]);

            if (f[to[k]]<f[u]+xy[to[k]]){

                f[to[k]]=f[u]+xy[to[k]];

                x2[to[k]]=;

                if (f[ans]<f[to[k]])

                    ans=to[k];

            }

            if (f[to[k]]==f[u]+xy[to[k]])

                x2[to[k]]=(x2[to[k]]+x2[u])%Mo;

            if (!w2[to[k]])

                rst[++t]=to[k];

        }

    }

    for(int i=;i<=n;i++)

        if (f[i]==f[ans])

            h2=(h2+x2[i])%Mo;

    printf("%d\n",f[ans]);

    printf("%d",h2);

    return ;

}