60分 求调
查看原帖
60分 求调
1268701
zhangzheng2026楼主2024/7/25 19:28

后面四个点WA

#include <bits/stdc++.h>
using namespace std;
long long n,m,p[100005],q[100005],h[100005],cnt,a[100005],cd[100005];
struct node{int next,to;}e[50000005];
void add(int x,int y)
{
	a[y]++;
	e[++cnt].to=y;
	e[cnt].next=h[x];
	h[x]=cnt;
}
priority_queue <int> pq;
long long gcd(long long x,long long y)
{
	while(y) x%=y,swap(x,y);
	return x;
}
void f(long long x,long long y)
{
	long long p1=p[x]*q[y]+p[y]*q[x],q1=q[y]*q[x];
	long long s=gcd(p1,q1);
	p[y]=p1/s,q[y]=q1/s;
}
int main()
{
	int x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		for(int j=1;j<=x;j++) cin>>y,add(i,y);
		cd[i]=x;
	}
	for(int i=1;i<=n;i++) q[i]=1;
	for(int i=1;i<=n;i++) if(!a[i]) p[i]=1,pq.push(-i);
	while(!pq.empty())
	{
		int k=-pq.top();
		pq.pop();
		if(!cd[k]) continue;
		q[k]*=cd[k];
		for(int i=h[k];i;i=e[i].next)
		{
			int kk=e[i].to;
			a[kk]--;
			f(k,kk);
			if(a[kk]==0) pq.push(-kk);
		}
	}
	for(int i=1;i<=n;i++) if(!cd[i]) cout<<p[i]<<" "<<q[i]<<'\n';
	return 0;
}
2024/7/25 19:28
加载中...