POJ2236 Wireless Network

　　并查集。本来看到N是10^3级别，操作数P是10^6级别，那么N*P就是O(10^9)级别，一阵后怕，不停寻找Plog(N)算法，后来实在想不出，看看时间限制是10s，直接上O(10^9)碰碰运气，没想到1Y，800多ms。

　　这样的话实现就很容易了，但是1Y后又交了几次，用C++编译器有时ac，有时wa；而用G++虽然时间会慢一点，但是一直都是AC，神马情况？！

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 1002
 4 
 5 int r[N][2], n, d, f[N];
 6 bool vis[N];
 7 
 8 int find_set(int x)
 9 {
10     return x == f[x] ? f[x] : f[x] = find_set(f[x]);
11 }
12 
13 inline bool inside(int i, int j)
14 {
15     return (r[i][0] - r[j][0]) * (r[i][0] - r[j][0]) + (r[i][1] - r[j][1]) * (r[i][1] - r[j][1]) <= d * d;
16 }
17 
18 void work()
19 {
20     int a, b, x, y, i, j;
21     char op[3];
22     while(scanf("%s", op) != EOF)
23     {
24         switch(op[0])
25         {
26             case 'O':
27                 scanf("%d", &j);
28                 vis[j] = true;
29                 for(i = 1; i <= n; i ++)
30                 {
31                     if(vis[i] && inside(i, j))
32                     {
33                         x = find_set(i);
34                         y = find_set(j);
35                         x < y ? f[y] = x : f[x] = y;
36                     }
37                 }
38                 break;
39             case 'S':
40                 scanf("%d%d", &a, &b);
41                 if(vis[a] && vis[b])
42                 {
43                     x = find_set(a);
44                     y = find_set(b);
45                     if(x == y)
46                         puts("SUCCESS");
47                     else 
48                         puts("FAIL");
49                 }
50                 else
51                     puts("FAIL");
52                 break;
53         }
54     }
55     
56 }
57 
58 void read()
59 {
60     scanf("%d%d", &n, &d);
61     for(int i = 1; i <= n; i ++)
62         scanf("%d%d", &r[i][0], &r[i][1]);
63 }
64 
65 void init()
66 {
67     memset(vis, false, sizeof vis);
68     for(int i = 0; i <= N; i ++)
69         f[i] = i;
70 }
71 
72 int main()
73 {
74     init();
75     read();
76     work();
77     return 0;
78 }