自测60pts(编译错误求助)
查看原帖
自测60pts(编译错误求助)
310579
east_li楼主2023/8/10 10:22
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> G[1000005];
struct fen{
	ll p=0,q=1;
}d[1000005];
queue <ll> q;
vector<ll> ans;
ll ru[1000005],t[1000005];
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
fen jia(fen x,fen y)
{
	fen res;
	res.p=x.p*y.q+x.q*y.p;
	res.q=x.q*y.q;
	ll gd=gcd(res.p,res.q);
	res.p=res.p/gd;
	res.q=res.q/gd;
	return res;
}
int main()
{
//	freopen("water.in","r",stdin);
//	freopen("water.out","w",stdout);
	ll n,m;
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)
	{
		ll v;
		scanf("%lld",&t[i]);
		if(t[i]==0)
		{
			ans.push_back(i);
		}
		if(i<=m)
		{
			d[i].p=1;
//			d[i].q=t[i];
		}
		for(ll j=1;j<=t[i];j++)
		{
			scanf("%lld",&v);
			G[i].push_back(v);
			ru[v]++;
		}
	}
	for(ll i=1;i<=m;i++)
	{
		q.push(i);
	}
	while(!q.empty())
	{
		ll u=q.front();
		q.pop();
		d[u].q=d[u].q*t[u];
//		cout<<d[u].q<<endl;
		for(auto v:G[u])
		{
//			printf("0");
			d[v]=jia(d[v],d[u]);
//			printf("%lld %lld ",d[u].p,d[u].q);
			ru[v]--;
			if(ru[v]==0&&t[v]!=0)
			{
				q.push(v);
			}
		}
//		printf("\n");
	}
	for(auto i:ans)
	{
		printf("%lld %lld\n",d[i].p,d[i].q);
	}
	return 0;
}
2023/8/10 10:22
加载中...