最后三个点tle,和题解第一篇比对了一下,不知道哪一步多花了时间
查看原帖
最后三个点tle,和题解第一篇比对了一下,不知道哪一步多花了时间
553601
乖,摸摸头楼主2022/5/13 15:20
#include <bits/stdc++.h>
using namespace std;

struct node {
	int fa = 0, x = 1, size = 1;
};

int main() {
	int t, x, y, l, r;
	char c;
	node f[30010];
	cin >> t;
	while (t--) {
		scanf("\n%c%d%d", &c, &x, &y);
		if (c == 'M') {
			while (f[x].fa) x = f[x].fa;
			while (f[y].fa) y = f[y].fa;
			f[x].fa = y;
			f[x].x = f[y].size;
			f[y].size += f[x].size;
		} else {
			l = f[x].x, r = f[y].x;
			while (f[x].fa) {
				x = f[x].fa;
				l += f[x].x;
			}
			while (f[y].fa) {
				y = f[y].fa;
				r += f[y].x;
			}
			if (x != y) {
				printf("-1\n");
			} else {
				printf("%d\n",abs(l - r)-1);
			}
		}
	}
	return 0;
}
2022/5/13 15:20
加载中...