萌新 缩点 五十二分 求助
查看原帖
萌新 缩点 五十二分 求助
281497
KEBrantily楼主2021/1/30 11:02

是在答案的统计方面出了错

取模没有问题,问题出在计数数组的更新过程中

感觉排查了各种问题以及换了多种写法,但是并没有找出错误

求调 谢谢

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define maxn 2000010
#define rr register 
#define debug cout<<"lkp ak ioi"<<endl;

using namespace std;

int t,n,m,tot,x;
int cnt,top,ans,sum,Tot;
bool vis[maxn],flag[maxn];
int num[maxn],siz[maxn],low[maxn];
int len[maxn],js[maxn],zhan[maxn];
int head[maxn],dfn[maxn],Head[maxn];
struct edge{int fr,to,nxt;}e[maxn];
struct Edge{int Fr,To,Nxt;}E[maxn];

int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*w;
}

inline void add(int fr,int to){
	e[++tot].to=to;
	e[tot].nxt=head[fr];
	head[fr]=tot;
}

inline void Add(int fr,int to){
	E[++Tot].To=to;
	E[Tot].Nxt=Head[fr];
	Head[fr]=Tot;
}

void tarjan(int u){
	low[u]=dfn[u]=++cnt;
	vis[u]=1;zhan[++top]=u;
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(!dfn[to]) tarjan(to),low[u]=min(low[u],low[to]);
		else if(vis[to]) low[u]=min(low[u],dfn[to]);
	}
	if(dfn[u]==low[u]){
		++siz[++t];
		int pre=zhan[top--];
		vis[pre]=0;num[pre]=t;
		while(pre!=u){
			++siz[t];pre=zhan[top--];
			vis[pre]=0;num[pre]=t;
		}
	}
}

void work(int u){
	for(int i=Head[u];i;i=E[i].Nxt){
		int to=E[i].To;
		if(flag[to]==u) continue;
		flag[to]=u;
        if(len[to]<len[u]+siz[to]){
		    len[to]=len[u]+siz[to];
            js[to]=js[u];
		}
		else if(len[to]==len[u]+siz[to])
	    	js[to]=(js[to]+js[u])%x;	
	}
}

int main(){
	n=read();m=read();x=read();
	for(int i=1,fr,to;i<=m;i++){fr=read();to=read();add(fr,to);}
	for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}
	for(int i=1;i<=n;i++){
		js[i]=1;len[i]=siz[i];
		for(int j=head[i];j;j=e[j].nxt){
			int to=e[j].to;
			if(num[to]!=num[i]) Add(num[i],num[to]);
		}
	}
	for(int i=t;i>=1;i--){work(i);}
	for(int i=1;i<=t;i++){
		if(len[i]>ans) ans=len[i],sum=js[i];
		else if(len[i]==ans) sum+=js[i],sum%=x;
	}
	printf("%d\n%d",ans,sum);
	return 0;
}
2021/1/30 11:02
加载中...