描述 Description
This summer, there is a worldwide competition being held in Chef Town and some of the best chefs of the world are participating. The rules of this competition are quite simple.
Each participant needs to bring his or her best dish. The judges will initially assign a score to each of the dishes. Now, several rounds will follow. In each round, any two chefs will be called up on the stage. Each of the chefs can then choose any one dish to battle against the other chef and the one having the dish with the higher score will win this round. The winner of the round will also obtain all the dishes of the loser who will then be eliminated. In case both the dishes have equal scores, this round will be considered as a tie and nothing else will happen. Note that initially each chef will have only one dish and all the chefs play the rounds optimally.
Your task is to simulate and answer some queries related to this. You will be given N dishes numbered from 1 to N with the ith dish belonging to the ith chef initially. You will also be given an array S where S[i] denotes the score given by the judges to the ith dish before starting the rounds. You will have to answer Q queries, each of which can be of the following types :
1. 0 x y : This denotes that the chef containing dish number x competes with the chef containing dish number y currently in this round. If a single chef is the owner of both the dishes, print “Invalid query!” (without quotes), otherwise execute and store the result of this round as described by the rules above.
2. 1 x : You need to output the index of the chef containing dish x at this point.
输入格式 InputFormat
First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of chefs in the contest. The next line contains N space separated integers where the ith integer represents S[i]. The next line contains an integer Q denoting the number of queries. Q lines follow where each line can be of the format 0 x y or 1 x as described in the problem statement.
输出格式 OutputFormat
For each test, print in each line the answer for the queries as described in the problem statement .
样例输入 SampleInput
1
2
1 2
2
0 1 2
1 1
样例输出 SampleOutput
2
并查集维护即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int T,q;
int fa[10005],a[10005];
int getfa(int s)
{
if (fa[s]==s) return s;
fa[s]=getfa(fa[s]);
return fa[s];
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]),fa[i]=i;
scanf("%d",&q);
for (i=1;i<=q;i++)
{
scanf("%d",&z);
if (z==1)
{
scanf("%d",&x);
printf("%d\n",getfa(x));
}
if (z==0)
{
scanf("%d%d",&x,&y);
if (getfa(x)==getfa(y)) printf("Invalid query!\n");
if (a[getfa(x)]==a[getfa(y)]) continue;
if (a[getfa(x)]>a[getfa(y)]) fa[getfa(y)]=x;
else fa[getfa(x)]=y;
}
}
}
return 0;
}