记录编号	158234	评测结果	AAAAAAAAAA
题目名称	[HDU 1512] 爱争吵的猴子	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.409 s
提交时间	2015-04-13 17:07:56	内存使用	2.99 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
priority_queue<int> strongest[100001];
int f[100001],a[100001],n,m;
int rank[100001];

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

void un(int x,int y)
{
	int p=find(x);
	int q=find(y);
	if (p==q) printf("%d\n",-1);
	else 
	{
		if (rank[p]>rank[q])
		{
			int t;
			t=p;
			p=q;
			q=t;
		}
		int strongp=strongest[p].top(); 
		strongest[p].pop();
		int strongq=strongest[q].top(); 
		strongest[q].pop();
		f[p]=q;	
		while (!strongest[p].empty())
		{
			strongest[q].push(strongest[p].top());
			strongest[p].pop();
		}
		strongest[q].push(strongp/2);
		strongest[q].push(strongq/2);
		printf("%d\n",strongest[q].top());
		rank[q]=rank[p]+rank[q];
	}
}

int main()
{
	freopen("monkeyk.in","r",stdin);
	freopen("monkeyk.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	 scanf("%d",&a[i]);
	for (int i=1;i<=n;++i)
	{
	 f[i]=i;
     strongest[i].push(a[i]);
     rank[i]=1;
    }
	scanf("%d",&m);
	int x,y;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		un(x,y);
	}
	return 0;
}