另外:时间限制?
by zhyh @ 2017-07-13 19:11:10
+1s 233333
by 磨面 @ 2017-07-13 20:15:55
其实就是读入的问题,比如碰见不严谨的数据,scanf就会读错
还有,最后三个点超时 了...
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
//%U37405
using namespace std;
```
int fth[30005],pre[30005],tail[30005],sum[30005],
```cpp
t,p1,p2,a,b,s1,s2;
char s,c;
inline void rord(char &opt, int &x, int &y)
{
opt = getchar();
while (!isupper(opt)) opt = getchar();
char ch = getchar();
int res[2] = {0};
for (int i = 0; i <= 1; i++)
{
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch))
{
res[i] = res[i] * 10 + ch - '0';
ch = getchar();
}
}
x = res[0], y = res[1];
}
int check(int j,int k){
return(sum[k]>sum[j]?(sum[k]-sum[j]-1):(sum[j]-sum[k]-1));
}
void combine(int j,int p,int k,int q){ //j(head[p to k(head[q
int tmp,f; f=tmp=tail[p];
pre[p]=tail[q];
do{sum[tmp]+=sum[tail[q]]; f=pre[f]; fth[tmp]=q; tmp=f;
}while(f!=tail[q]);
tail[q]=tail[p];
return;
}
int find(int k){
while(fth[k]!=k)k=fth[k];
return k;
}
int main(){
//freopen("testdata.in","r",stdin);
//freopen("output.out","w",stdout);
for(int i=1;i<=30000;i++){fth[i]=tail[i]=pre[i]=i;sum[i]=1;}
scanf("%d",&t);
while(t--){
rord(s, a, b);
s1=find(a);
s2=find(b);
// printf("s1s2tail: %d %d %d %d\n",s1,tail[a],s2,tail[b]);
if(s=='M'){
combine(a,s1,b,s2);
}else{
if(s1==s2)printf("%d\n",check(a,b));
else printf("-1\n");
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}//61分
```
by yxr811740686 @ 2017-08-29 10:48:56
超时的问题就是你合并的步骤太复杂,思考化简就好了
by yxr811740686 @ 2017-08-29 10:51:05