HDU - 2818
7167 ワード
Building Block
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3563 Accepted Submission(s): 1072
Problem Description
John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1...N.Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:
M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command.
C X : Count the number of blocks under block X
You are request to find out the output for each C operation.
Input
The first line contains integer P. Then P lines follow, each of which contain an operation describe above.
Output
Output the count for each C operations in one line.
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1 0 2
Source
2009 Multi-University Training Contest 1 - Host by TJU
Recommend
gaojie
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3563 Accepted Submission(s): 1072
Problem Description
John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1...N.Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:
M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command.
C X : Count the number of blocks under block X
You are request to find out the output for each C operation.
Input
The first line contains integer P. Then P lines follow, each of which contain an operation describe above.
Output
Output the count for each C operations in one line.
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1 0 2
Source
2009 Multi-University Training Contest 1 - Host by TJU
Recommend
gaojie
/***
: , ;
'M a b' a b ,
‘C a ' a
: 。
***/
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
using namespace std;
#define maxn 300000 + 3000
int fa[maxn]; ///
int sum[maxn]; ///
int under[maxn]; /// pile
int n;
void Init()
{
for(int i=0; i<=n; i++)
{
sum[i] = 1;
fa[i] = i;
}
memset(under,0,sizeof(under));
}
int Find(int u)
{
int tmp;
if(u != fa[u])
{
tmp = Find(fa[u]);
under[u] += under[fa[u]];
fa[u] = tmp;
}
return fa[u];
}
void Union(int x,int y)
{
int X,Y;
X = Find(x);
Y = Find(y);
if (X!=Y)
{
under[X] = sum[Y]; //X ( ) , under[]
sum[Y] += sum[X]; // Y ( ) ( Piles)
fa[X] = Y; //
}
}
int main()
{
while(~scanf("%d",&n))
{
Init();
char ch[10];
int u,v,w;
while(n--)
{
scanf("%s",ch);
if(ch[0] == 'M')
{
scanf("%d %d",&u,&v);
Union(u,v);
}
else
{
scanf("%d",&w);
Find(w);
printf("%d
",under[w]);
}
}
}
return 0;
}