90pts求助
查看原帖
90pts求助
1431223
SSerxhs01楼主2025/7/27 20:21

已开__int128,仍WA最后一个测试点,代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100009;
int n,m;
vector<vector<int>> adj(n+1);
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
struct Fraction{
    __int128 p,q;
    Fraction(int _p=0,int _q=1){
        int g=gcd(abs(_p),abs(_q));
        p=_p/g;
        q=_q/g;
        if(q<0)p=-p,q=-q;
        if(p==0)q=1;
    }
    static int gcd(int a,int b) {
        while(b){
			int t=b;
			b=a%b;
			a=t; 
		}
        return a;
    }
    static int lcm(int a,int b) {
        return a/gcd(a,b)*b;
    }
    Fraction operator+(const Fraction&o)const{
        int l=lcm(q,o.q);
        return {p*(l/q)+o.p*(l/o.q),l};
    }
    Fraction operator/(int d)const{
        return {p,q*d};
    }
};
signed main() {
    cin>>n>>m;
    vector<int>in_degree(n+1,0);
	vector<int>out_degree(n+1,0);
	vector<vector<int> >adj(n+1);
    for(int i=1,d;i<=n;i++){
        cin>>d;
        out_degree[i]=d;
        for(int j=0,a;j<d;j++){
            cin>>a;
            adj[i].push_back(a);
            in_degree[a]++;
        }
    }
    vector<Fraction> water(n+1,Fraction(0,1));
    queue<int> q;
    for(int i=1;i<=m;i++){
        water[i]=Fraction(1,1);
        q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(out_degree[u]==0)continue;
        Fraction divided=water[u]/out_degree[u];
        water[u]=Fraction(0,1);
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j];
            water[v]=water[v]+divided;
            in_degree[v]--;
            if(in_degree[v]==0){
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(out_degree[i]==0&&water[i].p!=0){
        	print(water[i].p);
			cout<<" ";
			print(water[i].q);
			cout<<endl; 
        }
    }
    return 0;
}

AC互关

2025/7/27 20:21
加载中...