求助 80分wa
查看原帖
求助 80分wa
151647
sycqwq楼主2021/8/20 11:11

rt

#include<bits/stdc++.h>
using namespace std;
#define int __int128
inline 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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int gcd(int x,int y)
{
    if(x<y)
    {
        swap(x,y);
    }   
    if(y==0)
        return x;
    return gcd(y,x%y);
}
struct node
{
    int fz,fm;
}a[100005];
int n,m;
vector<int> e[100005];
void add(node a,node &b)
{
	if(b.fm==0&&b.fz==0)
	{
		b=a;
		return;
	}
    b.fz=b.fm*a.fz+a.fm*b.fz;
    b.fm*=a.fm;
    int g=gcd(b.fm,b.fz);
//    cout<<g<<endl;
//    cout<<b.fz<<' '<<b.fm<<endl;
    b.fz/=g;
    b.fm/=g;
}
int bk[100005];
void cf(int a,node &b)
{
    int g=gcd(b.fz,a);
    a/=g;
    b.fz/=g;
    b.fm*=a;
}
void bfs(int x)
{
	queue<int> q;
	q.push(x);
	while(!q.empty())
	{
		int x=q.front();
//		cout<<x<<' '<<a[x].fz<<' '<<a[x].fm<<endl;
//		cout<<x<<endl;
		q.pop();
		bk[x]=0;
		for(int i=0;i<e[x].size();i++)
		{
			node t=a[x];
			cf(e[x].size(),t);
			add(t,a[e[x][i]]);
			if(bk[e[x][i]]==0)
			{
				bk[e[x][i]]=1;
				q.push(e[x][i]);
			}
		}
		if(e[x].size()!=0)	
			a[x].fz=a[x].fm=0;
	}
}
inline void out(int a)
{
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}
signed main()
{   
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        int x;
        x=read();
        for(int j=1;j<=x;j++)
        {
            int t;
            t=read();
            e[i].push_back(t);
        }
    }
    for(int i=1;i<=m;i++)
    {
        e[0].push_back(m);
    }
    a[0].fz=m;
    a[0].fm=1;
    bfs(0);
    for(int i=1;i<=n;i++)
    {
        if(e[i].size()==0)	
        {
        	out(a[i].fz);
        	cout<<' ';
        	out(a[i].fm);
        	cout<<endl;
		}
    }
    return 0;
}
2021/8/20 11:11
加载中...