[UOJ 121] Hzwer meteorite

[Title Description]:

After unremitting efforts, Hzwer summoned many meteorites. It is known that there are n areas on the map of Hzwer, and the ith meteorite fell in the ith area at the beginning. ndsf, who has an electric jet backpack, is proud. He thinks it's easy to move meteorites, so he moved all meteorites from some areas to other areas.

During ndsf's pleasant transportation, Hzwer wanted to know some information about meteorites. For each meteorite i asked by Hzwer, you must tell him that at this time, the number y of meteorites shared by meteorite i in area x and area x, and the number z of times meteorite i was transported.

[input description]:

The first line of input is a positive integer T. Indicates how many sets of input data there are.

Next, there are T groups of data. For each group of data, the first row contains two integers: N and Q.

Next, line Q, each line represents one handling or one inquiry, and the format is as follows:

T A B: it means that all meteorites in the area where ball A is located will be moved to the area where ball B is located.

Q A: Hzwer wants to know the x, y, z of meteorite a.

[output description]:

For the ith group of data, the first line outputs "Case i:" and then outputs x, y and z of each query operation. The answer of each query operation accounts for one line. There are no empty rows between each group of data.

[sample input]:

2
3 3
T 1 2
T 3 2
Q 2
3 4
T 1 2
Q 1
T 1 3
Q 1

[sample output]:

Case 1:
2 3 0
Case 2:
2 2 1
3 3 2

[time limit, data scope and description]:

Time: 1s space: 128M

20% data guarantee: 0 < = T < = 20, 2 < n < = 100, 2 < Q < = 100.

100% data guarantee: 0 < = T < = 100, 2 < n < = 10000, 2 < Q < = 10000.

For all data, ensure that AB is within the range of N and in different areas during handling operation.

 

Question solution: with power and collection, violence 90 points, the data is really water (wallpaper Yao Chen is really handsome, I love it

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
const int N=10003;
using namespace std;
int n,m,T,f[N],x,y;
char c;
struct node{
    int now;//Present position 
    int tot;//How many times 
}a[N];

void QGhappy(){
    for(int i=1;i<=n;i++) 
        { a[i].now=i; a[i].tot=0; }
    for(int i=1;i<=n;i++) f[i]=1;
}

void work1(){
    scanf("%d %d",&x,&y);
    int xx=a[x].now;
    int yy=a[y].now;
    for(int i=1;i<=n;i++){
        if(a[i].now==xx){
            a[i].now=yy;
            a[i].tot++;
        }
    }
    f[yy]+=f[xx]; f[xx]=0;
}

void work2(){
    int i; scanf("%d",&i);
    printf("%d %d %d\n",a[i].now,f[a[i].now],a[i].tot);
}

int main(){
    freopen("meteorite.in","r",stdin);
    freopen("meteorite.out","w",stdout); 
    scanf("%d",&T);
    for(int yc=1;yc<=T;yc++){
        printf("Case %d:\n",yc);
        scanf("%d %d",&n,&m);
        QGhappy(); //cout<<a[2].now;
        for(int i=1;i<=m;i++){
            cin>>c;
            if(c=='T') work1();
            else work2();
        }
    }
    return 0;
}

 

Tags: Union Find

Posted by sois on Fri, 13 May 2022 07:37:13 +0300