POJ 1962 - Corporative Network

http://poj.org/problem?id=1962

概要

\(N\) 個のノードがあり、\(Q\) 個の以下のような2種類の命令を処理する。 ここではあるノード I からエッジを辿っていった先のノードを center と呼ぶ。 またノード I とノード J の距離を \(|I - J| \% 1000\) とする。

• I I J: ノード I からノード J にエッジを張る。このとき I は center であったことが保証されている。
• E I: ノード I から I の center までの距離を答える。

制約

• \(5 \le N \le 2 \cdot 10 ^ 4\)
• \(1 \le Q \le 2 \cdot 10 ^ 5\)

解法

Union-Find っぽく、距離を聞かれたときに経路圧縮を行う。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct S
 7 {
 8   vector<int> parent, dist;
 9   S(int n) : parent(n, -1), dist(n, 0) {}
10   void link(int i, int j)
11   {
12     parent[i] = j;
13   }
14   pair<int,int> query(int i)
15   {
16     if (parent[i] == -1) {
17       return make_pair(dist[i], i);
18     } else {
19       const pair<int,int> r = query(parent[i]);
20       if (dist[i] == 0) {
21         dist[i] = r.first + abs(parent[i] - i) % 1000;
22       } else {
23         dist[i] += r.first;
24       }
25       parent[i] = r.second;
26       return make_pair(dist[i], parent[i]);
27     }
28   }
29 };
30 
31 int main()
32 {
33   int T;
34   scanf("%d", &T);
35   while (T-- > 0) {
36     int N;
37     scanf("%d", &N);
38     S s(N);
39     char buf[4];
40     while (scanf("%s", buf) != EOF && buf[0] != 'O') {
41       if (buf[0] == 'E') {
42         int i;
43         scanf("%d", &i);
44         --i;
45         printf("%d\n", s.query(i).first);
46       } else {
47         int i, j;
48         scanf("%d %d", &i, &j);
49         --i;  --j;
50         s.link(i, j);
51       }
52     }
53   }
54   return 0;
55 }