30pts?
查看原帖
30pts?
348511
原子げんし楼主2021/2/25 22:25

RT,怎么调都是30分

//7.21
//rng_58 bless me

#include<bits/stdc++.h>
using namespace std;
//define:
#define REP(i,n) for(int i = 0; i < n; i++)
#define ll __int128
#define y1 fgkhfkfhg
//const:
const int MAXN = 100010;
//something:
inline void write(ll x) {
    if(x < 0) {
    	putchar('-');
		x = -x;
	}
    if(x > 9)  {
		write(x / 10);
	}
    putchar(x % 10 + '0');
}
int __lcm(int x,int y) {
	return  x * y / __gcd(x,y);
}
struct node {
	ll x,y;//分子,分母 
	node() {}
	void iint() {
		x = 0; y = 1;
	}
	node(int X,int Y) {
		x = X; y = Y;
	}
};
node fun(node a,node b,int t) {
	ll x1 = a.x,y1 = a.y; ll x2 = b.x,y2 = b.y;
	//cout << x1 << '/' << y1 << '\n' << x2 << '/' << y2 << '\n';
	y2 *= t;
	int lcm = __lcm(y1,y2); x1 *= lcm / y1; x2 *= lcm / y2; y1 = y2 = lcm;
	x1 += x2;
	int gcd = __gcd(x1,y1);
	x1 /= gcd; y1 /= gcd;
	return node(x1,y1);
}
int N,M;
vector <int> g[MAXN],ord;
int deg[MAXN];
queue <int> q;
node dp[MAXN];
//run:
void solve() {
	cin >> N >> M;
	REP(i,N) {
		dp[i].iint();
		int K; cin >> K;
		if(!K) {
			ord.push_back(i);
		}
		while(K--) {
			int x; cin >> x; x--;
			g[i].push_back(x); deg[x]++;
		}
	}
	REP(i,N) {
		if(!deg[i]) {
			q.push(i); dp[i] = node(1,1);
		}
	}
	while(!q.empty()) {
		int x = q.front(); q.pop();
		//cout << x << ' ';
		REP(i,g[x].size()) {
			int nx = g[x][i]; deg[nx]--; int t = g[x].size();
			dp[nx] = fun(dp[nx],dp[x],t);
			if(!deg[nx]) {
				q.push(nx);
			}
		}
	}
	REP(i,ord.size()) {
		write(dp[ord[i]].x); putchar(' '); write(dp[ord[i]].y); puts("");
	}
}
//times:
void Times(int T) {
	while(T--) {
		solve();
	}
}
//begin:
int main() {
	int T = 1;
	//cin >> T;
	Times(T);
	return 0;
}
2021/2/25 22:25
加载中...