WA80
查看原帖
WA80
271736
Daidly楼主2021/7/27 15:04

最后两个过不了,确保程序思路无问题,只是 __int128 方面的问题,求助。

#include<bits/stdc++.h>
using namespace std;
#define int unsigned __int128
inline int read(){
    int x=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*w;
}
void print(int x){
    if(!x)return;
    if(x)print(x/10);
    putchar(x%10+'0');
}
int n,m,num,in[100005];
vector<int>e[100005];
int ans[100005],tmp;
struct node{
	int a,b;
}t[100005];
void topo(){
	queue<int>q;
	for(int i=1;i<=n;++i){
		if(!in[i]){
			q.push(i);
			t[i].a=1,t[i].b=1;
		}
	}
	while(!q.empty()){
		int u=q.front();
		ans[++tmp]=u;
		q.pop();
		for(int i=0;i<e[u].size();++i){
			int v=e[u][i];
			in[v]--;
			if(!in[v])q.push(v);
		}
	}
}
int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}
node add(int a,int b,int c,int d){
	node q;
	int lcm=b*d/gcd(b,d);
	a*=lcm/b,c*=lcm/d;
	q.a=a+c,q.b=lcm;
	int gcdd=gcd(q.a,q.b);
	q.a/=gcdd,q.b/=gcdd;
	return q;
}
node mul(int a,int b,int c,int d){
	node q;
	q.a=a*c,q.b=b*d;
	int gcdd=gcd(q.a,q.b);
	q.a/=gcdd,q.b/=gcdd;
	return q;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		num=read();
		int v;
		for(int j=1;j<=num;++j){
			v=read();
			e[i].push_back(v);
			in[v]++;
		}
	}
	topo();
	for(int i=1;i<=n;++i){
		if(!e[i].size())print(t[i].a),printf(" "),print(t[i].b),puts("");
		node ans=mul(t[i].a,t[i].b,1,e[i].size());
		for(int j=0;j<e[i].size();++j){
			int v=e[i][j];
			if(!t[v].a&&!t[v].b)t[v]=ans;
			else t[v]=add(t[v].a,t[v].b,ans.a,ans.b);
		}
	}
	return 0;
}
2021/7/27 15:04
加载中...