记录编号	559974	评测结果	AAAAAAAAAA
题目名称	[NOIP 2020]排水系统	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.429 s
提交时间	2021-03-31 20:55:11	内存使用	3.12 MiB

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define LL long long
#define LD long double
#define uLL unsigned long long
#define e 0.000000000001
using namespace std;
const int maxN = 1e5 + 10;

LD gcd(LD x, LD y);

int n, m;
int in[maxN], sorts[maxN];
pair <LD, LD> ans[maxN];
vector <LL> g[maxN];
queue <int> q;
int main(void){
	freopen("2020water.in", "r", stdin);
	freopen("2020water.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++){
		scanf("%d", &sorts[i]);
		for (int j = 1; j <= sorts[i]; j ++){
			int y;	scanf("%d", &y);
			g[i].push_back(y);
			in[y] ++;
		}
	}
	int s;
	for (int i = 1; i <= n; i ++)
		ans[i].second = 1;
	for (int i = 1; i <= n; i ++)
		if(!in[i])
			q.push(i), ans[i].first = 1, s = i;
	int x, y;
	while (q.size()){
		x = q.front();
		q.pop();
		for (int i = 0; i < g[x].size(); i ++){
			y = g[x][i];
			LD X = ans[x].first, Y = ans[x].second * sorts[x];
			LD gg = gcd(ans[y].second, Y);
			ans[y].first = ans[y].second / gg * X + Y / gg * ans[y].first;
			ans[y].second = ans[y].second / gg * Y;
			in[y] --;
			if (!in[y])
				q.push(y);
		}
	}
	for (int i = 1; i <= n; i ++){
		if (!sorts[i]){
			LD gg = gcd(ans[i].first, ans[i].second);
			printf("%.0Lf %.0Lf\n", ans[i].first / gg, ans[i].second / gg);
		}
	}
	return 0;
}

LD fl(LD x) {
	LD y = floor(x);
	if (y + 1.0 - e <= x)
		y++;
	return y;
}

LD gcd(LD x, LD y) {
	return (y >= -e && y <= e) ? x : gcd(y, x - fl(x / y) * y);
}