思路
用sum记录每个舰队的战舰数量, tohead 记录当前舰离舰首的距离,那么求任意两舰之间有多少舰显然就是 abs( tohead[i] - tohead[j] ) - 1;
CODE
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0) using namespace std;
typedef long long LL; template<class T>inline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
} namespace _buff {
const size_t BUFF = << ;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, , BUFF, stdin);
}
return ib == ie ? - : *ib++;
}
} int qread() {
using namespace _buff;
int ret = ;
bool pos = true;
char c = getc();
for (; (c < '' || c > '') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '' && c <= ''; c = getc()) {
ret = (ret << ) + (ret << ) + (c ^ );
}
return pos ? ret : -ret;
} const int maxn = 5e4 + ; int fa[maxn];
int tohead[maxn], sum[maxn];
int t; int fid(int x) {
if(fa[x] == x) {
return x;
}
int r1 = fa[x], r2 = fid(fa[x]);
fa[x] = r2;
tohead[x] += tohead[r1];
return r2;
} void join(int x, int y) {
int fx = fid(x), fy = fid(y);
fa[fy] = fx;
tohead[fy] = sum[fx];
sum[fx] += sum[fy];
sum[fy] = ;
} int main()
{
scanf("%d",&t);
for ( int i = ; i <= ; ++i ) {
fa[i] = i;
sum[i] = ;
}
while(t--) {
char s[];
int x, y;
cin >> s;
scanf("%d %d",&x, &y);
if(s[] == 'M') {
join(x, y);
}
else {
if(fid(x) != fid(y)) {
printf("-1\n");
continue;
}
else {
printf("%d\n",abs(tohead[x] - tohead[y]) - );
}
}
}
return ;
}