/ tabris /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 3ms 2.25 MiB
#2 Accepted 3ms 2.25 MiB
#3 Accepted 59ms 2.625 MiB
#4 Accepted 2ms 368.0 KiB
#5 Accepted 18ms 768.0 KiB
#6 Accepted 269ms 3.625 MiB

代码

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e5+5;
int pre[3*maxn],num[3*maxn],id[3*maxn];
int cnt;
int n,m;
int ans;
void init()
{
	cnt = n,ans = n;
	for(int i = 1;i <=3*n;++i)
	{
		pre[i] = i;
		num[i] = 1;
		id[i] = i;
	}
	return ;
 } 
int find(int x)
{
	return x==pre[x] ? x : pre[x] = find(pre[x]);
}
void join(int x,int y)
{
	int f1=find(x),f2=find(y);
	if(f1 != f2)
	{
		pre[f2] = f1;
		num[f1] += num[f2];
		ans--;
	}
	return ;
}
void del(int x)
{
	int f = find(id[x]);
	num[f]--;
	if(num[f]==0)
	ans--;
	cnt++;
	num[cnt] = 1;
	pre[cnt] = cnt;
	id[x] = cnt;
	ans++;
	return ;
}
int main()
{
	int _;
	cin>>_;
	char s[10];
	int ca = 1;
	while(_--)
	{
		scanf("%d %d",&n,&m);
		init();
		printf("Case #%d:\n",ca++);
		for(int i = 1; i<= m;++i)
		{
			scanf("%s",s);
			if(s[0]=='q')
			{
				printf("%d\n",ans);
			}
			else if(s[0] =='f')
			{
				int x,y;
				scanf("%d %d",&x,&y);
				int f1 = find(id[x]);
				int f2 = find(id[y]);
				if(f1 == f2)
				continue;
				if(num[f1] > num[f2])
				{
					printf("%d is winner!\n",x);
					join(id[x],id[y]);
				}
				else if(num[f1] < num[f2])
				{
					printf("%d is winner!\n",y);
					join(id[y],id[x]);
				}
				else
				printf("Either is winner!\n");
			}
			else if(s[0] =='t')
			{
				int x,y;
				scanf("%d %d",&x,&y);
				del(y);
				join(id[x],id[y]);
			}
			else if(s[0] =='r')
			{
				int x;
				scanf("%d",&x);
				del(x);
			}
		}
			
	}
	return 0;
}

信息

递交者
类型
递交
题目
测试用
语言
C++
递交时间
2017-09-11 12:46:38
评测时间
2017-09-11 12:46:38
评测机
分数
192
总耗时
357ms
峰值内存
3.625 MiB