为什么把int改成__int128就全部wa了啊
查看原帖
为什么把int改成__int128就全部wa了啊
638336
Defoliation楼主2022/11/16 17:41
#include<bits/stdc++.h>
#define maxn 100005
#define re register
#define il inline
using namespace std;
__int128 n,m,f[maxn],cnt,v;
vector<__int128>t[maxn];
vector<__int128>shuchu;
struct node{
	__int128 x,y;
}sum[maxn];
queue<__int128>q;
inline __int128 read(){   
    __int128 num=0,f=1;  
    char chr=getchar();
    while(chr<'0'||chr>'9'){   
        if(chr=='-') f=-1;
        chr=getchar();
    }
    while(chr>='0'&&chr<='9'){    
        num=num*10+chr-'0';   
        chr=getchar();
    } 
    return num*f;
}		
inline void write(__int128 tmp){
    char F[200];
    __int128 cnt=0 ;
    while(tmp>0){
    	F[cnt++]=tmp%10+'0';
        tmp/=10;
    }
    while(cnt>0) putchar(F[--cnt]);
}
		
		
__int128 g_cd(__int128 a,__int128 b){
	if(b==0){
		return a;
	}
	return g_cd(b,a%b);
}
signed main(){
	ios::sync_with_stdio(0);
	n=read();
	m=read();
	for(__int128 i=1;i<=n;i++){
		cnt=read();
		if(cnt==0){
			shuchu.push_back(i);
			continue;
		}
		for(__int128 j=1;j<=cnt;j++){
			v=read();
			t[i].push_back(v);
			f[v]++;
		}
	}
	for(__int128 i=1;i<=n;i++){
		if(f[i]==0){
			sum[i].x=sum[i].y=1;
			q.push(i);
			f[i]=-1;
		}
	}
	while(!q.empty()){
		__int128 pos=q.front();
		//cout<<pos<<endl;
		q.pop();
		__int128 fenzi=sum[pos].x;
		__int128 fenmu=sum[pos].y;
		//cout<<fenzi<<" "<<fenmu<<endl;
		for(__int128 i=0;i<t[pos].size();i++){
			f[t[pos][i]]--;
			if(f[t[pos][i]]==0){
				q.push(t[pos][i]);
				f[t[pos][i]]=-1;
			}
			if(sum[t[pos][i]].x==0){
				sum[t[pos][i]].x=fenzi;
				sum[t[pos][i]].y=fenmu*t[pos].size();
				__int128 c=g_cd(sum[t[pos][i]].x,sum[t[pos][i]].y);
				sum[t[pos][i]].x/=c;
				sum[t[pos][i]].y/=c;
			}
			else{
				//cout<<fenmu<<" "<<sum[t[pos][i]].y<<"aaaaaa"<<endl;
				//cout<<sum[t[pos][i]].x<<" "<<fenmu<<" "<<t[pos].size()<<" "<<fenzi<<" "<<sum[t[pos][i]].y<<"aaaa"<<endl;
				__int128 b=g_cd(sum[t[pos][i]].y,fenmu*t[pos].size());
				sum[t[pos][i]].x=fenmu*t[pos].size()/b*sum[t[pos][i]].x+sum[t[pos][i]].y/b*fenzi;
				sum[t[pos][i]].y*=(fenmu*t[pos].size()/b);
				__int128 c=g_cd(sum[t[pos][i]].x,sum[t[pos][i]].y);
				sum[t[pos][i]].x/=c;
				sum[t[pos][i]].y/=c;
			}
			//cout<<t[pos][i]<<" "<<sum[t[pos][i]].x<<" "<<sum[t[pos][i]].y<<endl;
		}
	}
	for(__int128 i=0;i<shuchu.size();i++){
		//cout<<shuchu[i]<<endl;
		__int128 x=sum[shuchu[i]].x;
		__int128 y=sum[shuchu[i]].y;
		//cout<<x<<" "<<y<<endl;
		//cout<<g_cd(x,y)<<endl;
		__int128 c=g_cd(x,y);
		x/=c;
		y/=c;
		write(x);
		cout<<" ";
		write(y);
		cout<<"\n";
	}
	return 0;
}

2022/11/16 17:41
加载中...