Peking University Online Judge 2236 Wireless Network
制限時間は10秒なので安心してください。
Union Find木、隣接リストを使って愚直に実装しても通ります。
#include<cstdio> #include<vector> #include<algorithm> using namespace std; static const int MAX_N = 1001; int N, D; int x[MAX_N], y[MAX_N]; vector<int> G[MAX_N]; bool fixed[MAX_N]; int par[MAX_N]; int rnk[MAX_N]; void init(int n){ for(int i = 0; i < n; i++){ par[i] = i; rnk[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(rnk[x] < rnk[y]){ par[x] = y; }else{ par[y] = x; if(rnk[x] == rnk[y]) rnk[x]++; } } bool same(int x, int y){ return find(x) == find(y); } int main(){ scanf("%d %d", &N, &D); for(int i = 0; i < N; i++) scanf("%d %d", &x[i], &y[i]); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(i == j) continue; if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= D * D){ G[i].push_back(j); G[j].push_back(i); } } } init(N); fill(fixed, fixed + N, false); for(;;){ char ch; if(scanf("%c", &ch) == EOF) break; if(ch == 'O'){ int p; scanf("%d", &p); p--; fixed[p] = true; for(int i = 0; i < G[p].size(); i++){ if(fixed[G[p][i]] == true) unite(p, G[p][i]); } }else if(ch == 'S'){ int p, q; scanf("%d %d", &p, &q); p--; q--; if(same(p, q)) printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }