- 银河英雄传说
code
- @ 2026-2-7 11:15:15
void solve() {
const int n = 30000;
vector<int> f(n + 1), w(n + 1), sz(n + 1);
for (int i = 1; i <= n; i++) f[i] = i, w[i] = 0, sz[i] = 1;
function<pair<int, int>(int)> find = [&] (int u)->pii {
if (u == f[u]) {
return {u, 0};
}
auto [root, wfather] = find(f[u]);
f[u] = root;
w[u] = wfather + w[u];
return {root, w[u]};
};
auto merge = [&] (int u, int v) {
auto [fu, lenu] = find(u);
auto [fv, lenv] = find(v);
if (fu == fv) return;
f[fu] = fv;
w[fu] = sz[fv];
sz[fv] += sz[fu];
};
auto query = [&] (int u, int v) {
auto [fu, lenu] = find(u);
auto [fv, lenv] = find(v);
if (fu != fv) return -1;
return abs(lenu - lenv) - 1;
};
int m;
cin >> m;
while (m--) {
char o;
int x, y;
cin >> o >> x >> y;
if (o == 'M') {
merge(x, y);
} else {
cout << query(x, y) << '\n';
}
}
}
0 条评论
目前还没有评论...
信息
- ID
- 426
- 时间
- ms
- 内存
- MiB
- 难度
- 5
- 标签
- 递交数
- 19
- 已通过
- 14
- 上传者