UESTC_秋实大哥打游戏 2015 UESTC Training for Data Structures<Problem H>

H - 秋实大哥打游戏

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

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

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

现在，秋实大哥发现了

每一次，秋实大哥会选择两个不同的小岛

把这两片小岛合并为一个新的集合，中心为

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

Input

第一行有一个整数

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

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

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

Output

对于每一次询问，输出一个整数，即

Sample input and output

Sample Input	Sample Output
3 I 1 2 E 1 I 3 1 E 3 O	1 3

解题报告

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

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 typedef long long ll;
 6 using namespace std;
 7 const ll maxn = 6e5 + 50;
 8 /*
 9 Dis is the distance between node and his root
10 */
11 ll pre[maxn];
12 ll dis[maxn]; 
13 
14 ll getfather(ll cur)
15 {
16    if (cur == pre[cur])
17     return cur;
18    ll fat = getfather(pre[cur]);
19    dis[cur] += dis[pre[cur]];
20    pre[cur] = fat;
21    return fat;
22 }
23 
24 char temp[150000];
25 
26 int main(int argc,char *argv[])
27 {
28   ll n;
29   scanf("%lld",&n);
30   memset(dis,0,sizeof(dis));
31   for(int i = 1 ; i <= n ; ++ i)
32    pre[i] = (ll)i;
33   while(1)
34    {
35          scanf("%s",temp);
36          if (temp[0] == 'O')
37           break;
38          if (temp[0] == 'I')
39           {
40                 ll x,y;
41                 scanf("%lld%lld",&x,&y);
42                 if (getfather(y) != x)
43                  {
44                   dis[x] = abs(x-y) % 1000;
45                   pre[x] = y;
46                  }
47        }
48       else
49        {
50              ll x;
51              scanf("%lld",&x);
52              getfather(x); // caculate ans
53              printf("%lld
",dis[x]);
54        }
55    }
56   return 0;
57 }

No Pain , No Gain.