30pts 7re求调
查看原帖
30pts 7re求调
500542
lvyongfeng楼主2024/11/26 14:50
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline int read() {
	char c = getchar();
	ull res = 0;
	while(c < '0' || c > '9') {
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = (res << 1) + (res << 3) + (c ^ 48);
		c = getchar();
	}
	return res;
}
inline void write(ull i) {
	if(i > 9)	write(i / 10);
	putchar((i % 10) + '0');
}
const int N = 1e7 + 5;
ull n, m, du[N], ans[N], up[N], down[N], zz[N];
vector<ull> vec[10];
queue<int>q;
ull gcd(ull a, ull b) {
	if(a % b)	return gcd(b, a % b);
	return b;
}
ull lcm(ull a, ull b) {
	ull g = gcd(a, b);
	return a * b / g;
}
void add(int a, int b) {
//	cout<<b<<':';
//	cout<<up[b]<<' '<<down[b]<<endl;
	ull l = lcm(down[a], down[b]);
	int k  = down[b];
	down[b] = l;
	ull _a = l / down[a];
	up[b] *= l / k;
	up[b] += up[a] * _a;

	return;
}
int main() {
//	freopen("water.in","r",stdin);
//	freopen("water.out","w",stdout);
	n = read();
	m = read();
	int num = 0;
	for(int i = 1; i <= n; i++) {
		int a, b;
		a = read();
		if(a == 0) {
			num ++;
			zz[num] = i;
		}
		for(int j = 1; j <= a; j++) {
			b = read();
			vec[i].push_back(b);
			du[b]++;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(du[i] == 0) {
			q.push(i);
			up[i] = 1;
		}
	}
	for(int i = 0; i <= 1e5; i++)	down[i] = 1;
	while(!q.empty()) {
		int k = q.front();
		q.pop();
		if(!vec[k].empty()) {
			down[k] *= vec[k].size();
			for(int i = 0; i < vec[k].size(); i++) {
				du[vec[k][i]]--;
				//cout<<k<<':'<<up[k]<<' '<<down[k]<<' '<<vec[k][i]<<':'<<up[vec[k][i]]<<' '<<down[vec[k][i]]<<endl;
				add(k, vec[k][i]);
				//cout<<vec[k][i]<<':'<<up[vec[k][i]]<<' '<<down[vec[k][i]]<<endl;
				if(du[vec[k][i]] == 0) {
					//cout<<"vec:"<<vec[k][i]<<endl;
					q.push(vec[k][i]);
				}
			}
		}
	}
//	for(int i = 1; i <= n; i++) {
//		cout<<up[i]<<' ';
//	}
//	cout<<endl;
//	for(int i = 1; i <= n; i++) {
//		cout<<down[i]<<' ';
//	}
	for(int i = 1; i <= num; i++) {
		ull u = up[zz[i]], d = down[zz[i]];
		ull g = gcd(u, d);
		u /= g;
		d /= g;
		write(u);
		putchar(' ');
		write(d);
		putchar('\n');
	}

	return 0;
}
/*
5 1
3 2 3 5
2 4 5
2 5 4
0
0
*/

2024/11/26 14:50
加载中...