60分超时4个点求助
查看原帖
60分超时4个点求助
366468
_Z_Y_X_SWS楼主2022/10/20 20:52
#include <bits/stdc++.h>
using namespace std ;
const int N=100005;
struct aaaa {
	unsigned long long fz,fm;
}a[N];
bool b[N];
unsigned long long rd[N],cd[N],h[10000005],num;
unsigned long long gcd (unsigned long long m,unsigned long long n){
	while (n!=0){
		unsigned long long t=m%n;
		m=n,n=t;
	}
	return m;
}
unsigned long long n,m;
aaaa yf (aaaa ss){
	unsigned long long l=gcd (ss.fm,ss.fz);
	ss.fm/=l;
	ss.fz/=l;
	return ss;
}
aaaa add (aaaa x,aaaa y){
	unsigned long long l=gcd(x.fm,y.fm);
	unsigned long long ll=x.fm/l*y.fm;
	aaaa ss;
	ss.fm=ll;
	ss.fz=x.fz*ll/x.fm+y.fz*ll/y.fm;
	return yf (ss);
}
struct edge {
	unsigned long long to,next;
}d[100000005];
void ct (unsigned long long a,unsigned long long b){
	d[++num].to=b;
	d[num].next=h[a];
	h[a]=num;
}
int main (){
	scanf ("%llu%llu",&n,&m);
	for (unsigned long long i=1;i<=n;i++){
		scanf ("%llu",&cd[i]);
		for (unsigned long long j=1;j<=cd[i];j++){
			unsigned long long x;
			cin>>x;
			ct (i,x);
			rd[x]++;
		}
	}
	for (unsigned long long i=1;i<=n;i++){
		if (rd[i]==0){
			a[i].fz=1;
			a[i].fm=1;
		}
	}
	
	while (1){
		bool o=0;
		unsigned long long k=0;
		for (unsigned long long i=1;i<=n;i++){
			if (b[i]==0&&rd[i]<=0&&cd[i]){
				k=i;
				o=1;
				break;
			}
		}
		if (!o){
			break;
		}
		b[k]=1;
		a[k].fm*=cd[k];
		a[k]=yf(a[k]);
		for (unsigned long long i=h[k];i!=0;i=d[i].next){
			
			rd[d[i].to]--;
			if (a[d[i].to].fz==0){
				a[d[i].to]=a[k];
			}
			else {
				a[d[i].to]=add (a[k],a[d[i].to]);
			}
		}
		
	}

	for (unsigned long long i=1;i<=n;i++){
		if (cd[i]==0){
			printf ("%llu %llu\n",a[i].fz,a[i].fm);

		}
	}
	return 0;
}
2022/10/20 20:52
加载中...