萌新求助,WA了4个点
查看原帖
萌新求助,WA了4个点
305013
orange_dream楼主2022/8/18 14:17

后几个点Wa掉了,输出挺离谱的

不是爆long long的问题

#include<bits/stdc++.h>
#define int unsigned long long 
using namespace std;
int n,m,num[100005],in[100005],x,dx[100005],dy[100005];
queue<int> q;
vector<int> G[100005];
int gcd(int x,int y){
	if (!y)return x;
	return gcd(y,x%y);
}
signed main(){
	scanf("%llu%llu",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%llu",&num[i]);
		for (int j=1;j<=num[i];j++){
			scanf("%llu",&x);
			G[i].push_back(x);
			in[x]++;
		}
	}
	for (int i=1;i<=n;i++){
		if (in[i]==0){
			q.push(i);
			dx[i]=1;
			dy[i]=1;
		}else{
			dy[i]=1;
			dx[i]=0;
		}
	}
	while (!q.empty()){
		int x=q.front();
		q.pop();
		int dxx=dx[x],dyy=dy[x]*G[x].size();
		int GCD=gcd(dxx,dyy);
		dxx/=GCD;dyy/=GCD;
		for (int i=0;i<G[x].size();i++){
			int v=G[x][i];
			//dx[v]/dy[v]+dxx/dyy=(dxx*dy[v]+dx[v]*dyy)/(dxx*dy[v]);
			int to_dx=(dxx*dy[v]+dx[v]*dyy),to_dy=(dyy*dy[v]);
			dx[v]=to_dx;dy[v]=to_dy;
			int GCD_v=gcd(dx[v],dy[v]);
			dx[v]/=GCD_v;dy[v]/=GCD_v;
			in[v]--;
			if (in[v]==0)q.push(v);
		}
	}
	for (int i=1;i<=n;i++){
		if (G[i].size()==0){
			printf("%llu %llu\n",dx[i],dy[i]);
		}
	}
	return 0;
}
2022/8/18 14:17
加载中...