这份代码在洛谷能通过,在AcWing上不能:
#include<bits/stdc++.h>
using namespace std;
const int N = 30009;
int t;
int fa[N];
int siz[N],dis[N];
int father(int x){
if(x == fa[x])
return x;
int root = father(fa[x]);
dis[x] += dis[fa[x]];
return fa[x] = root;
}
void join(int x,int y){
int fa_x = father(x),fa_y = father(y);
fa[fa_x] = fa_y;
dis[fa_x] = siz[fa_y];
siz[fa_y] += siz[fa_x];
}
int query(int x,int y){
int fa_x = father(x),fa_y = father(y);
if(fa_x == fa_y)
return abs(dis[x] - dis[y]) - 1;
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> t;
for(int i = 1;i < N;i++){
fa[i] = i;
siz[i] = 1;
}
while(t--){
string op;
int i,j;
cin >> op >> i >> j;
if(op == "M")
join(i,j);
else
cout << query(i,j) << '\n';
}
return 0;
}
in:
4
M 2 3
C 1 2
M 2 4
C 4 4
out:
-1
0