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;
}