【UOJ 121】Hzwer的陨石

【题目描述】:

经过不懈的努力,Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域,且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪,他认为搬陨石很容易,所以他将一些区域的陨石全搬到了另外一些区域。

在ndsf愉快的搬运过程中,Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i,你必须告诉他,在当前这个时候,i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。

【输入描述】:

输入的第一行是一个正整数T。表示有多少组输入数据。

接下来共有T组数据,对于每组数据,第一行包含两个整数:N和Q。

接下来Q行,每行表示一次搬运或一次询问,格式如下:

T A B:表示搬运,即将所有在A号球所在地区的陨石都搬到B号球所在地区去。

Q A:Hzwer想知道A号陨石的x,y,z。

【输出描述】:

对于第i组数据,第一行输出“Case i:”接下来输出每一个询问操作的x,y,z,每一个询问操作的答案占一行。每组数据之间没有空行。

【样例输入】:

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

【样例输出】:

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

【时间限制、数据范围及描述】:

时间:1s 空间:128M

20%的数据保证:0<=T<=20,2<N<=100,2<Q<=100。

100%的数据保证:0<=T<=100,2<N<=10000,2<Q<=10000。

对于所有数据保证搬运操作中AB在N的范围内且所在区域不相同。

 

题解:带权并查集,暴力90分,数据确实水的可以(壁纸姚琛真帅我爱了

#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;//现在位置 
    int tot;//搬运几次 
}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;
}

 

上一篇:UOJ#48. 【UR #3】核聚变反应强度 数学


下一篇:UOJ #513 [UR #19]清扫银河 (图论、线性基)