开了__int128都是WA后六个点
查看原帖
开了__int128都是WA后六个点
914335
xiongmy123楼主2024/11/1 18:23
#include <bits/stdc++.h>
using namespace std;
#define int __int128
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		print(x/10);
	}
	putchar(x%10+'0');
}
const int MN=5e5+5;
int n,m,rd[MN];
struct node{
	int up,down;
}water[MN];
vector<int> push_in[MN],push_out;
queue<int> q;
int gcd(int a,int b){
	if(a%b==0){
		return b;
	}
	return gcd(b,a%b);
}
node add(node a,node b){
	int son1=a.up,son2=b.up,mo1=a.down,mo2=b.down;
	node ans;
	if(son2==0||mo2==0){
		ans={son1,mo1};
		return ans;
	}
	int son=son1*mo2+son2*mo1,mo=mo1*mo2;
//	cout<<son<<" "<<mo<<endl;
	ans.up=son;
	ans.down=mo;
//	cout<<ans.up<<" "<<ans.down<<endl;
	int g=gcd(son,mo);
	ans.up/=g;
	ans.down/=g;
	return ans;
}
void topo(){
	while(!q.empty()){
		int u=q.front();
		q.pop();
		int len=push_in[u].size();
		for(int i=0;i<len;i++){
			int v=push_in[u][i];
			node t={water[u].up,water[u].down*len};
			water[v]=add(t,water[v]);
//			cout<<water[v].up<<" "<<water[v].down<<endl;
//            cout<<water[v].up<<" "<<water[v].down<<endl;
			rd[v]--;
			if(rd[v]==0)q.push(v);
		}
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		int p;
		p=read();
		if(p==0){
			push_out.push_back(i);
			continue;
		}
		for(int j=1;j<=p;j++){
			int q;
			q=read();
			push_in[i].push_back(q);
			rd[q]++;
		}
	}
	for(int i=1;i<=n;i++){
		if(rd[i]==0){
			q.push(i);
			water[i]={1,1};
		}
	}
	topo();
//	for(int i=1;i<=n;i++){
//		cout<<water[i].up<<" "<<water[i].down<<endl;
//	}
	for(int i=0;i<push_out.size();i++){
		int u=push_out[i];
		print(water[u].up);
		cout<<" ";
		print(water[u].down);
		cout<<endl;
	}
	return 0;
}
2024/11/1 18:23
加载中...