90分最后一点WA
查看原帖
90分最后一点WA
977890
nanami0721楼主2024/11/22 12:32

能不开int__128吗

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,p[100010],q[100010],num[100010],num2[100010][6],r[100010],k1,l2,r2,h1;
queue<unsigned long long>ans;
long long gcd(unsigned long long a, unsigned long long b) {
while (b != 0) {
unsigned long long t1 = b;
b = a % b;
a = t1;
}
return a;
}
void pd(unsigned long long &l1,unsigned long long &r1,unsigned long long l2,unsigned long long r2){
	h1=gcd(r1,r2);
	l1*=r2/h1;
	l2*=r1/h1;
	r1*=r2/h1;
	l1+=l2;
	h1=gcd(l1,r1);
	l1=l1/h1;
	r1=r1/h1;
}
int main(){
	cin>>n>>m;
	for(unsigned long long i=1;i<=n;i++){
		cin>>num[i];
		if(i<=m){
			p[i]=1;
			q[i]=1;
		}
		for(unsigned long long j=1;j<=num[i];j++){
			cin>>num2[i][j];
			r[num2[i][j]]++;
		}
		
	}
	for(unsigned long long i=1;i<=n;i++){
		if(r[i]==0){
			ans.push(i);
			
		}
	}
	while(!ans.empty()){
		k1=ans.front();
		ans.pop();
		l2=p[k1];
		r2=q[k1]*num[k1];
		//printf("%lld %lld\n",l2,r2);
		//l2=p[k1]/gcd(p[k1],num[k1]);
		//r2=r2*(num[k1]/gcd(p[k1],num[k1]));
		for(long long i=1;i<=num[k1];i++){
			if(l2!=0){
				if(p[num2[k1][i]]==0){
					h1=gcd(l2,r2);
					p[num2[k1][i]]=l2/h1;
					q[num2[k1][i]]=r2/h1;
				}
				else {
					pd(p[num2[k1][i]],q[num2[k1][i]],l2,r2);
				}
			}
			//printf("%lld %lld %lld\n",k1,p[num2[k1][i]],q[num2[k1][i]]);
			r[num2[k1][i]]--;
			if(r[num2[k1][i]]==0&&num[num2[k1][i]]){
				ans.push(num2[k1][i]);
			}
		}
		
	}
	for(long long i=1;i<=n;i++){
			if(num[i]==0){
				cout<<p[i]<<" "<<q[i]<<"\n";
			}
		}
	return 0;
} 
2024/11/22 12:32
加载中...