秋实大哥打游戏

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/59

Description

”也许人生就是游戏，你却执意耕耘着春秋。” —— 秋实大哥叹道。

秋实大哥是一个喜欢玩游戏的人，相较于其他种类的游戏，秋实大哥更喜欢自由开放的沙盒游戏，尤其是minecraft。

现在，秋实大哥发现了N个独立的小岛（编号1,2,3.....N)，于是他要把这些小岛连起来。

每一次，秋实大哥会选择两个不同的小岛x（x是所在集合的中心）和y（y不一定是集合的中心），如果小岛x和小岛y不在一个集合里，就建立一条距离为|x−y| mod 1000的边，

把这两片小岛合并为一个新的集合，中心为y原来所在的集合中心。

但，秋实大哥想实时知道某一个小岛距当前所在集合中心的距离。由于秋实大哥忙着过节，所以他想请你帮忙。

Input

第一行有一个整数N表示小岛的个数。

接下来有若干行，每一行为以下两种操作中的一种：

I x y : 表示秋实大哥想要在x和y之间建立一条边。
E x : 询问x到当前集合中心的距离。

输入以一个大写字母O结束。

1≤N≤100000，操作数≤200000。

Output

对于每一次询问，输出一个整数，即x到当前集合中心的距离，占一行。

Sample Input

3
I 1 2
E 1
I 3 1
E 3
O

Sample Output

1
3

HINT

题意

题解：

简简单单的带权并查集

每次往上更新的时候，顺便把边权更新了就好

记住得路径压缩

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 100010

int mod=;

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("\n");

}

*/

//**************************************************************************************

int p[maxn];

long long w[maxn];

int fi(int x)

{

    if(p[x]==x) return x;

    else

    {

        fi(p[x]);

        w[x]+=w[p[x]];

        p[x]=fi(p[x]);

    }

    return p[x];

}

bool un(int a,int b)

{

    int x=fi(a);

    int y=fi(b);

    if(x==y)

        return false;

    p[a]=y;

    w[a]=abs(a-b)%+w[b];

    return true;

}

int main()

{

        int n,x,y;

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            p[i]=i;

            w[i]=;

        }

        char a[];

        while(scanf("%s",&a)!=EOF)

        {

            if(a[]=='O')

                break;

            if(a[]=='E')

            {

                scanf("%d",&x);

                fi(x);

                printf("%lld\n",w[x]);

            }

            else

            {

                scanf("%d%d",&x,&y);

                un(x,y);

            }

        }

    return ;

}

秋实大哥

2015 UESTC 数据结构专题H题 秋实大哥打游戏 带权并查集