UESTC_秋实大哥打游戏 2015 UESTC Training for Data Structures

时间：2021-12-28 16:19:28

H - 秋实大哥打游戏

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

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

秋实大哥是一个喜欢玩游戏的人，相较于其他种类的游戏，秋实大哥更喜欢*开放的沙盒游戏，尤其是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 and output

Sample Input Sample Output 
3

I 1 2

E 1

I 3 1

E 3

O
 
1

3

解题报告

容易联想到并查集，使用dis[]数组来维护每个点到根的距离，唯一需要注意的是先修改距离,再更新其父亲，否则会出错.

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 typedef long long ll;

 using namespace std;

 const ll maxn = 6e5 + ;

 /*

 Dis is the distance between node and his root

 */

 ll pre[maxn];

 ll dis[maxn]; 

 ll getfather(ll cur)

 {

    if (cur == pre[cur])

     return cur;

    ll fat = getfather(pre[cur]);

    dis[cur] += dis[pre[cur]];

    pre[cur] = fat;

    return fat;

 }

 char temp[];

 int main(int argc,char *argv[])

 {

   ll n;

   scanf("%lld",&n);

   memset(dis,,sizeof(dis));

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

    pre[i] = (ll)i;

   while()

    {

          scanf("%s",temp);

          if (temp[] == 'O')

           break;

          if (temp[] == 'I')

           {

                 ll x,y;

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

                 if (getfather(y) != x)

                  {

                   dis[x] = abs(x-y) % ;

                   pre[x] = y;

                  }

        }

       else

        {

              ll x;

              scanf("%lld",&x);

              getfather(x); // caculate ans

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

        }

    }

   return ;

 }

相关文章