萌新妺子刚学OI,NOIP2020T1求调
查看原帖
萌新妺子刚学OI,NOIP2020T1求调
536439
YONIC楼主2022/8/24 17:10

好吧那上面其实不是妹而是妺

#include<bits/stdc++.h>
using namespace std;
int n,m,v[(int)(1e5+3)];
unsigned long long gcd(int a,int b){return b?gcd(b,a%b):a;}
struct fraction{unsigned long long m,d;}w[(int)(1e5+3)];
fraction add(fraction a,fraction b){
	fraction c;
	c.d=a.d/gcd(a.d,b.d)*b.d;
	c.m=c.d/a.d*a.m+c.d/b.d*b.m;
	return c;
}
vector<int>G[(int)(1e5+3)];
void DFS(int u){
	fraction t=w[u];
	t.d*=G[u].size();
	for(int i=0;i<G[u].size();++i){
		w[G[u][i]]=add(w[G[u][i]],t);
		if(v[G[u][i]]!=2) DFS(G[u][i]);
	}
	w[u].m=0;
    w[u].d=1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) v[i]=1;
    for(int i=1;i<=n;++i){
    	int x;
    	scanf("%d",&x);
    	if(!x) v[i]=2;
        int y;
    	while(x--){
    		scanf("%d",&y);
    		G[i].push_back(y);
    		if(v[y]!=2) v[y]=0;
		}
	}
	for(int i=1;i<=n;++i) w[i].m=0,w[i].d=1;
    for(int i=1;i<=n;++i) if(v[i]==1) w[i].m=w[i].d=1,DFS(i);
	for(int i=1;i<=n;++i) if(v[i]==2) printf("%llu %llu\n",w[i].m/gcd(w[i].m,w[i].d),w[i].d/gcd(w[i].m,w[i].d));
	return 0;
}
2022/8/24 17:10
加载中...