Submission #1096319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096319		vjudge1	Inside information (BOI21_servers)	C++14	0 / 100	165 ms	1648 KiB

servers

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,k;
struct node{
	int val;
	int siz;
}fa[maxn]; 
int find(int x){
	return x==fa[x].val?x:find(fa[x].val);
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy)return ;
	int sizx=fa[fx].siz,sizy=fa[fy].siz;
	if(fa[fx].siz<fa[fy].siz)swap(fx,fy);
	fa[fy].val=fx;
	fa[fx].siz=sizx+sizy;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		fa[i].val=i;
		fa[i].siz=1;
	}
	for(int i=1;i<=n+k-1;i++){
		char op;
		cin>>op;
		if(op=='S'){
			int a,b;cin>>a>>b;
			merge(a,b);
		}
		else if(op=='Q'){
			int a,b;cin>>a>>b;
			int fx=find(a),fy=find(b);
			if(fx==fy)cout<<"yes\n";
			else cout<<"no\n";
		}
		else {
			int a;
			cin>>a;
			int f=find(a);
			cout<<fa[f].siz<<'\n';
		}
	}
	return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5