POJ(PKU) 2236 Wireless Network

顕著なunion-find

実行速度遅すぎる。

#include <cstdio>
#include <iostream>

using namespace std;

int par[1002];//親
int rank[1002];//木の深さ

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank[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(rank[x] < rank[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank[x] == rank[y])rank[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}
  
  
  
  

int main(){
  int n,f;
  int d[1003][3]={0};
  
  scanf("%d%d",&n,&f);
  
  for(int i = 1;i <= n;i++){
    scanf("%d%d",&d[i][0],&d[i][1]);
    d[i][2] = 0;
  }
  
  init(n);
  
  char t;
  
  while(cin >> t){

    
    if(t == 'O'){
      int p;
      scanf("%d",&p);
      
      d[p][2] = 1;
      
      int x = d[p][0];
      int y = d[p][1];
      
      for(int i = 1;i <= n;i++){
	if(d[i][2] != 1)continue;
	if(i == p)continue;
	
	int xx = d[i][0];
	int yy = d[i][1];
	
	if((x-xx)*(x-xx) + (y-yy)*(y-yy) <= f*f){
	  unite(p,i);
	}
      }
      
    }else{
      int p,q;
      
      scanf("%d%d",&p,&q);
      
      if(same(p,q)){
	printf("SUCCESS\n");
      }else{
	printf("FAIL\n");
      }
    }
  }
  
  return 0;
  
}