本机过不了样例提交AC
  • 板块学术版
  • 楼主__frj
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/8/12 16:07
  • 上次更新2023/10/27 15:46:01
查看原帖
本机过不了样例提交AC
89338
__frj楼主2022/8/12 16:07

这道题 我的代码在本机无法通过样例,在luogu IDE上可以通过,且提交AC

求原因 附上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<unordered_set>
#define LL long long 
using namespace std;


int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int M = 1e6+7 , N = 1e5+7;
int n,m,mod;
int tot = 0,scc_cnt = 0 , cnt = 0 , top = 0;
int h1[N],n1[M],t1[M],h2[N],n2[M],t2[M];
int id[N],dfn[N],st[N],ins[N],siz[N],low[N];
void add1(int x,int y){
	t1[++tot] = y , n1[tot] = h1[x] , h1[x] = tot;
}
void add2(int x,int y){
	t2[++tot] = y , n2[tot] = h2[x] , h2[x] = tot;
}
void tarjan(int x){
	dfn[x] = low[x] = ++cnt;
	st[++top] = x , ins[x] = 1;
	for(int i=h1[x];i;i=n1[i]){
		int y = t1[i];
		if(!dfn[y]){
			tarjan(y);
			low[x] = min(low[x],low[y]);
		}
		if(ins[y]){
			low[x] = min(low[x],dfn[y]);
		}
	}
	if(dfn[x] == low[x]){
		scc_cnt ++;
		int y;
		while(x != y){
			y = st[top--];
			ins[y] = 0;
			id[y] = scc_cnt;
			siz[scc_cnt] ++;
		} 
	} 
} 
int f[N],g[N];
int main(){
	n = read() , m = read() , mod = read();
	for(int i=1;i<=m;i++){
		int x = read() , y = read();
		add1(x,y);
	}	
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i); 
		}
	}
	tot = 0;
	unordered_set<LL> S; 
	for(int i=1;i<=n;i++){
		for(int j=h1[i];j;j=n1[j]){
			int k = t1[j];
			int a = id[i] , b = id[k];
			LL h = a*1145140ll + b; 
			if(a!=b && !S.count(h)){
				add2(a,b);
				S.insert(h);
			}
		}
	}
	for(int i=scc_cnt;i>=1;i--){
		if(!f[i]){
			f[i] = siz[i];
			g[i] = 1;
		}
		for(int j=h2[i];j;j=n2[j]){
			int y = t2[j];
			if(f[y] < f[i] + siz[y]){
				f[y] = f[i] + siz[y];
				g[y] = g[i];
			}
			else if(f[y] == f[i] + siz[y]){
				g[y] += g[i];
				g[y] %= mod;
			}
		}
	}
	int maxf = -1919810 , sg = 0;
	for(int i=1;i<=scc_cnt;i++){
		if(maxf < f[i]){
			sg = g[i];
			maxf = f[i];
		}
		else if(maxf == f[i]){
			sg = (sg + g[i]) % mod;
		}
	}
	printf("%d\n%d",maxf,sg);
	return 0;
}
2022/8/12 16:07
加载中...