rt,t1在考场上打了2h,过了大样例就不管了,结果。。。大红大紫(大雾)
#include <bits/stdc++.h>
#include <cstdio>
#define rep(a, b, c) for(int a = b; a <= c; ++ a)
using namespace std;
typedef unsigned long long ll;
const ll MAXN = 100005, MAXM = 15;
ll n, m, d[MAXN];
struct NODE {
ll fz, fm; //分子,分母
} water[MAXN]; //water记录当前每个节点有多少污水
ll out[MAXN]; //记录哪个节点可以排出污水,1表示可以排出污水
vector<ll> v[MAXN]; //v存每个节点的子节点
inline ll READ() {
ll f = 1, res = 0;
char ch;
ch = getchar();
while((ch < '0' || ch > '9')) {
if(ch == '-') f = -1;
ch = getchar();
}
while((ch >= '0' && ch <= '9')) {
res = res * 10 + ch - '0';
ch = getchar();
}
return res * f;
}
ll gcd(ll x, ll y) {
return ((y == 0) ? (x) : (gcd(y, x % y)));
}
inline NODE add(NODE a, NODE b) {
NODE res;
if(a.fm > b.fm) {
swap(a, b);
}
if(a.fz == 0 && a.fm == 0) {
return b;
}
else if(b.fz == 0 && b.fm == 0) return a;
ll t = gcd(a.fm, b.fm);
ll z1, z2, m1;
z1 = a.fz * (b.fm / t);
z2 = b.fz * (a.fm / t);
m1 = a.fm * (b.fm / t);
res.fz = z1 + z2;
res.fm = m1;
ll t1 = gcd(res.fz, res.fm);
res.fz /= t1;
res.fm /= t1;
return res;
}
int main() {
//freopen("water.in", "r", stdin); freopen("water.out", "w", stdout);
n = READ();
m = READ();
rep(i, 1, m) water[i].fz = 1, water[i].fm = 1;
rep(i, 1, n) {
ll x;
x = READ();
if(x == 0) {
out[i] = 1;
continue;
}
rep(j, 1, x) {
ll y;
y = READ();
v[i].push_back(y);
}
}
rep(i, 1, n) {
if(out[i] == 1) continue;
ll sz = v[i].size();
if(sz == 0) continue;
ll fz = water[i].fz, fm = water[i].fm * sz;
NODE tt;
tt.fz = fz;
tt.fm = fm;
water[i].fz = 0, water[i].fm = 0;
rep(j, 0, sz - 1) {
water[v[i][j]] = add(water[v[i][j]], tt);
}
}
rep(i, 1, n) {
if(out[i] == 1) {
//ll t = gcd(water[i].fz, water[i].fm);
cout << water[i].fz << ' ' << water[i].fm << endl;
}
}
return 0;
}
/*
5 1
3 2 3 5
2 4 5
2 5 4
0
0
1 3
2 3
*/
下面是代码麻烦大佬看看怎么回事