求助
  • 板块灌水区
  • 楼主pengbonan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/9 12:50
  • 上次更新2024/6/9 15:43:30
查看原帖
求助
1005693
pengbonan楼主2024/6/9 12:50

P4971

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e6 + 10;
int n, m;
int lc[N], rc[N], dist[N], fa[N];
bool tf[N]; 
long long t, w, k, v[N];
int find (int x) {
	if (fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}
int merge (int x, int y) {
	if (!x || !y) return x | y;
	if (v[x] < v[y]) swap(x, y);
	rc[x] = merge(rc[x], y);
	if (dist[lc[x]] < dist[rc[x]]) swap(lc[x], rc[x]);
	dist[x] = dist[rc[x]] + 1;
	return x;
}
void Delete (int x) {
	int a = lc[x], b = rc[x];
	fa[a] = a, fa[b] = b;
	lc[x] = rc[x] = 0;
	dist[x] = 0;
	merge(merge(a, b), find(x));
}
void clear () {
	fa[0] = lc[0] = rc[0] = 0;
	dist[0] = -1;
	memset(tf, 0, sizeof tf);
}
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cin >> t >> w >> k;
	while (t --) {
		clear();
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) {
			cin >> v[i];
			fa[i] = i;
			rc[i] = lc[i] = dist[i] = 0;
		}
		while (m --) {
			int f, a, b;
			cin >> f;
			if (f == 2) {
				cin >> a;
				v[a] = 0;
				Delete(a);
			} else if (f == 3) {
				cin >> a >> b;
				a = find(a);
				v[a] -= min(v[a], 1ll * b);
				Delete(a);
			} else {
				cin >> a >> b;
				a = find(a);
				b = find(b);
				if (a == b) continue;
				merge(a, b);
			}
		}
		long long sum = 0, M = 0;
		for (int i = 1; i <= n; i ++) {
			int root = find(i);
			if (tf[root]) continue;
			v[root] = 1;
			M = max(M, v[root]);
			sum += v[root];
		}
		if (w == 2) sum -= M;
		if (w == 3) sum += M;
		if (sum == 0) cout << "Gensokyo 0\n";
		else if (sum <= k) cout << "Heaven " << sum << '\n';
		else cout << "Hell " << sum << '\n';
	}
	return 0;
}
2024/6/9 12:50
加载中...