MnZn刚学配对堆,WA70pts求助
  • 板块P1456 Monkey King
  • 楼主strcmp
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/4/9 21:39
  • 上次更新2023/10/28 04:08:42
查看原帖
MnZn刚学配对堆,WA70pts求助
551861
strcmp楼主2022/4/9 21:39

rt,都是too short on xx line,请问是哪里写挂了吗?

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N = 4e5 + 10;
struct node {
	int son, sub;
	ll val;
}heap[N];
int cnt = 0, n, m, a, b, rt = 0;
#define son(x) (heap[x].son)
#define sub(x) (heap[x].sub)
#define val(x) (heap[x].val)
int unset[N];
inline int newnode(ll val) {
	heap[cnt].val = val;
	return cnt++;
}
int find(int x) {
	if (unset[x] == x)return x;
	return unset[x] = find(unset[x]);
}
inline int merge(int x, int y) {
	if (!x || !y)return x | y;
	if (val(y) > val(x))swap(x, y);
	sub(y) = son(x), son(x) = y;
	unset[y] = x;
	return x;
}
int merges(int x) {
	int s = sub(x), ss = sub(s);
	unset[x] = x, unset[s] = s, unset[ss] = ss;
	sub(x) = 0, sub(s) = 0;
	if (!x || !s)return x | s;
	return merge(merge(x, s), merges(ss));
}
inline int del(int x) { 
	x = find(x);
	unset[son(x)] = son(x); int k = son(x); son(x) = 0;
	return merges(k); 
}
inline int unmerge(int x, int y) {
	x = find(x), y = find(y);
	return unset[x] = unset[y] = merge(x, y);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();
	cin >> n; ll res = 0;
	for (int i = 1; i <= n; i++)cin >> heap[i].val, unset[i] = i;
	cin >> m;
	while (m--) {
		cin >> a >> b;
		if (find(a) == find(b)) { cout << -1 << endl; continue; }
		rt = unmerge(a, b);
		int d = del(rt); heap[rt].val >>= 1;
		cout << heap[rt].val << endl;
		rt = merge(rt, d);
	}
	return 0;
}
2022/4/9 21:39
加载中...