POJ 2236 - Wireless Network

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

概要

\(N\) 台のコンピュータがそれぞれ二次元座標上の格子点 \((x_i, y_i)\) にあり、初期状態ではすべて壊れている。 2台のコンピュータは、距離 \(D\) 以下でどちらも修復されていれば、直接通信することができる。 また、別のコンピュータを経由して通信することもできる。 このとき、

• \(p\) 番目のコンピュータを修復する
• \(p\) 番目のコンピュータと \(q\) 番目のコンピュータは通信できるか?

という2種類の \(M\) 個のクエリに答える。

制約

• \(1 \le N \le 1001\)
• \(0 \le D \le 20000\)
• \(1 \le M \le 300000\)

解法

コンピュータが壊れているか修復済みかの状態を更新しながら Union-Find するだけ。

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 struct DisjointSet/*{{{*/
 6 {
 7   vector<int> parent;
 8 
 9   int root(int x)
10   {
11     if (parent[x] < 0) {
12       return x;
13     } else {
14       parent[x] = root(parent[x]);
15       return parent[x];
16     }
17   }
18 
19   explicit DisjointSet(int n) : parent(n, -1) {}
20 
21   bool unite(int x, int y)
22   {
23     const int a = root(x);
24     const int b = root(y);
25     if (a != b) {
26       if (parent[a] < parent[b]) {
27         parent[a] += parent[b];
28         parent[b] = a;
29       } else {
30         parent[b] += parent[a];
31         parent[a] = b;
32       }
33       return true;
34     } else {
35       return false;
36     }
37   }
38 
39   bool find(int x, int y) { return root(x) == root(y); }
40   int size(int x) { return -parent[root(x)]; }
41 };/*}}}*/
42 
43 int main()
44 {
45   int N, D;
46   scanf("%d %d", &N, &D);
47   vector<pair<int,int> > v(N);
48   for (int i = 0; i < N; i++) {
49     scanf("%d %d", &v[i].first, &v[i].second);
50   }
51 
52   vector<vector<int> > g(N, vector<int>(N, false));
53   for (int i = 0; i < N; i++) {
54     for (int j = 0; j < N; j++) {
55       const int x = v[i].first - v[j].first;
56       const int y = v[i].second - v[j].second;
57       g[i][j] = x*x + y*y <= D*D;
58     }
59   }
60 
61   vector<int> repaired(N, false);
62   char cmd[8];
63   int p;
64   DisjointSet s(N);
65   while (scanf("%s %d", cmd, &p) != EOF) {
66     --p;
67     if (*cmd == 'S') {
68       int q;
69       scanf("%d", &q);
70       --q;
71       puts(s.find(p, q) ? "SUCCESS" : "FAIL");
72     } else {
73       if (!repaired[p]) {
74         repaired[p] = true;
75         for (int i = 0; i < N; i++) {
76           if (g[p][i] && repaired[i]) {
77             s.unite(p, i);
78           }
79         }
80       }
81     }
82   }
83   return 0;
84 }