90pts,求助
查看原帖
90pts,求助
374077
一只小阿离楼主2022/8/16 17:07

这道题是要用高精度吗?第10个点错了

#include<bits/stdc++.h>
#define LL unsigned long long
using namespace std;
LL gcd(LL x,LL y)
{
	if(y==0) return x;
	else return gcd(y,x%y);
}
struct frac
{
	LL x,y;
	frac()
	{
		x=0,y=1;
	}
	friend frac operator+ (const frac &p,const frac &q)
	{
		frac ans;
		LL t=gcd(p.y,q.y);
		ans.x=q.y/t*p.x+p.y/t*q.x;
		ans.y=p.y/t*q.y;
		t=gcd(ans.x,ans.y);
		ans.x/=t,ans.y/=t;
		return ans;
	}
};
struct edge
{
	int v,next;
}e[500010];
int m,n,x,cnt;
int d[100010],ind[100010],head[100010];
frac ans[100010];
queue <int> q;
void addedge(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
	
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&d[i]);
		for(int j=1;j<=d[i];j++)
		{
			scanf("%d",&x);
			ind[x]++,addedge(i,x);
		}
	}
	for(int i=1;i<=n;i++)
		if(ind[i]==0)
			q.push(i),ans[i].x=1;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		if(d[now]) ans[now].y*=d[now];
		for(int i=head[now];i;i=e[i].next)
		{
			int v=e[i].v;
			ans[v]=ans[v]+ans[now];
			ind[v]--;
			if(ind[v]==0)
				q.push(v);
		}
	}
	for(int i=1;i<=n;i++)
		if(d[i]==0)
			printf("%llu %llu\n",ans[i].x,ans[i].y);
}




















2022/8/16 17:07
加载中...