洛谷P5092 [USACO2004OPEN]Cube Stacking 方块游戏 (带权并查集)

题目描述

约翰和贝茜在玩一个方块游戏。编号为 1\ldots n 1…n 的 n n ( 1 \leq n \leq 30000 1≤n≤30000 )个方块正放在地上，每个构成一个立方柱。

游戏开始后，约翰会给贝茜发出 P (1≤P≤100000 )个指令。指令有两种：

移动(M)：将包含X的立方柱移动到包含Y的立方柱上。

统计(C)：统计含X的立方柱中，在X下方的方块数目。

写个程序帮贝茜完成游戏。

输入输出格式

输入格式：

第1行输入 P ，之后 P 行每行输入一条指令，形式为“M X Y”或者“C X”。

输入保证不会有将立方柱放在自己头上的指令。

输出格式：

输出共 P 行，对于每个统计指令，输出其结果。

输入输出样例

输入样例#1：

6

M 1 6

C 1

M 2 4

M 2 6

C 3

C 4

输出样例#1：

1

0

2

这个作为带权并查集的模板，来复习一下。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1200000;

int n, fa[N], dis[N], siz[N], x, y;

char opt;

int find(int x) {

	if (fa[x] == x)

		return x;

	int which = find(fa[x]);

	dis[x] += dis[fa[x]];

	fa[x] = which;

	return which;

}

signed main() {

	cin >> n;

	for (int i = 1; i <= 30000; i++) {

		fa[i]=i;

		siz[i] = 1;

	}

	while (n--) {

		cin >> opt;

		if (opt == 'M') {

			cin >> x >> y;

			int xx=find(x),yy=find(y);

			fa[xx]=yy;

			dis[xx] += siz[yy];

			siz[yy] += siz[xx];

		} else if (opt == 'C') {

			cin >> x;

			find(x);

			cout << dis[x] << '\n';

		}

	}

	return 0;

}

巴特西

洛谷P5092 [USACO2004OPEN]Cube Stacking 方块游戏 (带权并查集)

最新文章

热门文章