22pts求调
查看原帖
22pts求调
1156169
liuxuanrui000楼主2025/1/21 16:44
#include<iostream>
using namespace std;
const int N=30007;
int f[N],s[N],k[N],l[N];
int fa(int u){
	int ans=0;
	if(f[u]==u){
		return u;
	}
	ans=fa(f[u]);
	k[u]=max(k[l[u]]+1,k[u]);
	f[u]=ans;
	return ans;
} 
int son(int u){
	if(s[u]==u){
		return u;
	}
	return s[u]=son(s[u]);
}
int main(){
	int t,n=30000,i,j,fi,sj;
	char c;
	cin>>t;
	for(i=1;i<=n;i++){
		f[i]=s[i]=l[i]=i;
		k[i]=1;
	}
	while(t--){
		cin>>c>>i>>j;
		if(c=='M'){
			fi=fa(i),sj=son(j);
			f[fi]=sj;
			s[sj]=fi;
			l[fi]=sj;
		}
		else{
			if(fa(i)==fa(j)){
				cout<<max(k[i],k[j])-min(k[i],k[j])-1<<endl;
			}
			else{
				cout<<-1<<endl;
			}
		} 
	}
	return 0;
}
2025/1/21 16:44
加载中...