KEBrantily @ 2021-01-30 11:02:42
是在答案的统计方面出了错
取模没有问题,问题出在计数数组的更新过程中
感觉排查了各种问题以及换了多种写法,但是并没有找出错误
求调 谢谢
#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;
}
by iMya_nlgau @ 2021-01-30 11:09:10
是不是没处理重边?
by KEBrantily @ 2021-01-30 11:18:26
@Sapphire6575737973
解决了 不是这个问题
我的 flag[]
定义了 bool
类型然而调用的是 int
类型的
我一开始的写法这么用是可以的,后来换了写法,应该是我为了省事直接调过去用然后忘改了
还是谢谢您帮我看
此贴终