我恨大样例
  • 板块学术版
  • 楼主lao_lihiOI
  • 当前回复8
  • 已保存回复8
  • 发布时间2020/12/6 15:36
  • 上次更新2023/11/5 06:30:53
查看原帖
我恨大样例
317650
lao_lihiOI楼主2020/12/6 15:36

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
*/

下面是代码麻烦大佬看看怎么回事

2020/12/6 15:36
加载中...