TLE 1个,求优化
查看原帖
TLE 1个,求优化
197603
ygl666666楼主2020/12/5 18:06
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
using namespace std;
long long n,m,ta[1000001],tb[1000001],a[1000001],k[1000001];
long long gcd(long long x,long long y){
	if(y==0){
		return x;
	}
	if(x<y){
		return gcd(y,x);
	}else{
		return gcd(y,x%y);
	}
}
int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		ta[i]=1,tb[i]=1;	
	}
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==0){
			k[i]=1;
			continue;
		}
		for(long long j=1;j<=a[i];j++){
			long long b;
			cin>>b;
			if(ta[b]!=0&&tb[i]!=0){
				long long x=ta[b],y=tb[b],xx=ta[i],yy=a[i]*tb[i];
				long long gbs=y*yy/gcd(y,yy);
				x=gbs/yy*xx+gbs/y*x;
				y=gbs;
				long long z=x;
				x/=gcd(x,y);
				y/=gcd(z,y);
				ta[b]=x,tb[b]=y;
			}else{
				ta[b]=ta[i],tb[b]=a[i]*tb[i];
				long long z=ta[b];
				ta[b]/=gcd(ta[b],tb[b]);
				tb[b]/=gcd(z,tb[b]);
			}
		}
	}
	
	for(long long i=1;i<=n;i++){
		if(k[i]){
			long long z=ta[i];
			ta[i]/=gcd(ta[i],tb[i]);
			tb[i]/=gcd(z,tb[i]);
			cout<<ta[i]<<" "<<tb[i]<<endl;
		}
	}
	return 0;
}

2020/12/5 18:06
加载中...