66分求调
查看原帖
66分求调
559847
Ferm_Tawn楼主2023/12/1 18:01

超时了

#include<bits/stdc++.h>
using namespace std;
char c;
int maxn;
int t , fa[30005] , siz1[30005] , siz2[30005];
int find(int xx){
	if(xx == fa[xx]) return xx;
	else return fa[xx] = find(fa[xx]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	for(int i = 1 ; i <= 30000 ; i++) fa[i] = i , siz1[i] = 1 , siz2[i] = -1;
	while(t--){
		cin >> c;
		int x , y;
		if(c == 'M'){
			cin >> x >> y;
			maxn = max(maxn , max(x , y));
			int o1 = find(x) , o2 = find(y);
			for(int i = 1 ; i <= 30000 ; i++){
				if(find(i) == o1){
					siz2[i] += siz1[o2];
				}
			}
			siz1[o2] += siz1[o1];
			siz1[o1] = siz1[o2];
			fa[o1] = o2;
		}
		else{
			cin >> x >> y;
			if(find(x) == find(y)) cout << max(0 , abs(siz2[y] - siz2[x]) - 1) << endl;
			else cout << "-1\n";
		}

	}
	return 0;
}
2023/12/1 18:01
加载中...