3 条题解
-
2
#include<bits/stdc++.h> using namespace std; int fa[30001],front[30001],num[30001],x,y,i,j,n,T,ans; char ins; int find(int n){ if(fa[n]==n)return fa[n]; int fn=find(fa[n]); front[n]+=front[fa[n]]; return fa[n]=fn; } int main(){ cin>>T; for(i=1;i<=30000;++i){ fa[i]=i; front[i]=0; num[i]=1; } while(T--){ cin>>ins>>x>>y; int fx=find(x); int fy=find(y); if(ins=='M'){ front[fx]+=num[fy]; fa[fx]=fy; num[fy]+=num[fx]; num[fx]=0; } if(ins=='C'){ if(fx!=fy)cout<<"-1"<<endl; else cout<<abs(front[x]-front[y])-1<<endl; } } return 0; }
-
1
#include <cstdio> #include <cctype> #include <cmath> const int M=30000; int n; int f[M+10],dis[M+10]; int size[M+10]; inline int read(void) { int x=0; char c=getchar(); for (;!isdigit(c);c=getchar()); for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x; } int findf(int i) { if (f[i]==i) return i; int pre=f[i],anc=findf(f[i]); f[i]=anc,dis[i]+=dis[pre]; return anc; } int main(void) { n=read(); for (int i=1;i<=M;i++) f[i]=i,size[i]=1; char c; int x,y; int fx,fy; for (int i=1;i<=n;i++) { scanf("\n"); c=getchar(); x=read(),y=read(); fx=findf(x),fy=findf(y); if (c=='M') { f[fx]=fy; dis[fx]=size[fy]; size[fy]+=size[fx]; } else printf("%d\n",fx!=fy?-1:dis[x]<dis[y]?dis[y]-dis[x]-1:dis[x]-dis[y]-1); } return 0; }
-
0
#include <bits/stdc++.h> using namespace std; const int n=30000; int m,k,s,t,fa[n+5],size[n+5],d[n+5],ss,tt; int getfa(int x){ if (fa[x]==x) return x;//当前是根节点,直接返回x int p=getfa(fa[x]);//p 是根节点 d[x]+=d[fa[x]];//此时的fa[x]已经指向了p,d[fa[x]]中保存的是fa[x]到p的距离 //d[x]+=d[fa[x]]就可以得到x到p的距离了 fa[x]=p;//更新fa[x] return p; } int main() { cin>>m; for (int i=1;i<=n;++i){ fa[i]=i; size[i]=1; } char c; for (int i=1;i<=m;++i){ c=getchar(); while (c!='C' && c!='M') c=getchar(); cin>>x>>y; s=getfa(x); t=getfa(y); if (c=='C'){ if (s!=t) cout<<-1<<endl;//不在同一列 else cout<<abs(d[x]-d[y])-1<<endl;//在同一列输出距离差 } else { fa[s]=t; d[s]=size[t];//整体排在以t为根的集合后面,首元素s距离t有size[t]的距离 size[t]+=size[s]; } } }
- 1
信息
- ID
- 217
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 80
- 已通过
- 40
- 上传者