萌新求助T1
  • 板块学术版
  • 楼主Prean
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/12/5 18:21
  • 上次更新2023/11/5 06:37:14
查看原帖
萌新求助T1
160839
Prean楼主2020/12/5 18:21

在 oitiku 上挂成了 50pts,有无神仙能帮忙找找错/kel

#include<cstdio>
#define DEBUG printf("Baylor AK IOI!!!\n");
typedef unsigned long long ll;
const int M=1e5+5;
int n,m,d[M],it[M],to[M][6];
ll gcd(const ll&a,const ll&b){
	return b?gcd(b,a%b):a;
}
inline ll lcm(const ll&a,const ll&b){
	return a/gcd(a,b)*b;
}
struct Ans{
	ll a,b;
	Ans(const ll&a=0,const ll&b=0):a(a),b(b){}
	inline Ans operator+(const Ans&it)const{
		ll LCM=lcm(b,it.b),ta=LCM/b,tb=LCM/it.b;
		return Ans(a*ta+it.a*tb,LCM);
	}
	inline Ans operator/(const int&it)const{
		ll GCD=gcd(a,b*it);
		return Ans(a/GCD,b*it/GCD);
	}
}ans[M],tmp[M];
inline void Solve(){
	register int T,i,u,v;
	for(u=1;u<=n;++u)tmp[u].a=0,tmp[u].b=1;
	for(T=1;T<=10;++T){
		for(u=1;u<=n;++u){
			if(!ans[u].a)continue;
			for(i=1;i<=d[u];++i){
				v=to[u][i];
				tmp[v]=tmp[v]+ans[u]/d[u];
			}
		}
		for(u=1;u<=n;++u){
			if(d[u])ans[u]=tmp[u];
			else ans[u]=ans[u]+tmp[u];
			tmp[u].a=0;tmp[u].b=1;
		}
	}
}
signed main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	register int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)ans[i].a=1;
	for(i=1;i<=n;++i)ans[i].b=1;
	for(i=1;i<=n;++i){
		scanf("%d",d+i);
		for(j=1;j<=d[i];++j)scanf("%d",to[i]+j);
	}
	Solve();
	for(i=1;i<=n;++i){
		if(!d[i]){
			ll tmp=gcd(ans[i].a,ans[i].b);
			printf("%lld %lld\n",ans[i].a/tmp,ans[i].b/tmp);
		}
	}
}
/*
5 1
3 2 3 5
2 4 5
2 5 4
0
0
*/
2020/12/5 18:21
加载中...