OItiku90pts luogu20pts求助
查看原帖
OItiku90pts luogu20pts求助
247842
zhenji_190127楼主2020/12/6 10:00

只开了long long

先后乘除差别真的这么大嘛?

#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int n,m;
vector<int >edge[100001];
int in[100001]={};
void add(int a,int b)
{
	edge[a].push_back(b);
	in[b]++; 
}
struct ELE
{
	long long tot,div;
}node[100001];
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
ELE water_plus(long long tot1,long long div1,long long tot2,long long div2)
{
	long long g1=gcd(div1,div2);
	long long tot=tot1*(div2/g1)+tot2*(div1/g1);
	long long div=div1*(div2/g1);
	long long g2=gcd(tot,div);
	return ELE{tot/g2,div/g2};
}
void run()
{
	priority_queue<int >Q;
	for(int i=1;i<=m;i++)
	{
		Q.push(-i);
		node[i].tot=1;
		node[i].div=1;
	}
	for(int i=m+1;i<=n;i++)
	{
		node[i].tot=0;
		node[i].div=1; 
	}
	while(!Q.empty())
	{
		int cur=-Q.top();
		Q.pop();
		long long tot1=node[cur].tot;
		long long div1=node[cur].div;
		int out=edge[cur].size();
		long long g=gcd(tot1,div1); 
		if(out==0)
		{
			printf("%lld %lld\n",tot1/g,div1/g);
			continue;
		}
		div1=div1*out;
		for(int i=0;i<out;i++)
		{
			int to=edge[cur][i];
			node[to]=water_plus(tot1,div1,node[to].tot,node[to].div);
			in[to]--;
			if(in[to]==0)
				Q.push(-to);
		}
	}
}
int main()
{
//	freopen("water.in","r",stdin);
//	freopen("water.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int tot;
		scanf("%d",&tot);
		for(int j=1;j<=tot;j++)
		{
			int to;
			scanf("%d",&to);
			add(i,to);
		}
	}
	run();
	return 0;
}
2020/12/6 10:00
加载中...