P1196 学习笔记

省流：带权并查集

题目传送门

带一个飞船与其所在列队头的距离就行了。

code

#include <bits/stdc++.h>
#define DEBUG
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;constexpr int mod = 998244353;
constexpr int maxn = 30005;int t, x, y;
char opt;int fa[maxn], front[maxn], siz[maxn];int find(int x){if (x == fa[x])return x;int findx = find(fa[x]);front[x] += front[fa[x]];return fa[x] = findx; // 带权的话会有点长
}void merge(int x, int y){int findx = find(x), findy = find(y);if (findx == findy)return;front[findx] += siz[findy];siz[findy] += siz[findx];siz[findx] = 0;fa[findx] = findy; // 带权的话会有点长
}int main() {fast;cin >> t;for (int i = 1; i <= maxn - 5; i++)fa[i] = i, siz[i] = 1;while (t--){cin >> opt >> x >> y;if (opt == 'C')if (find(x) != find(y))cout << -1 << endl;else cout << abs(front[x] - front[y]) - 1 << endl; // 输出距离，记得-1！！elsemerge(x, y);}return 0;
}