PKU 2236 Wireless Network
http://poj.org/problem?id=2236
union-findについての勘違いに気づかせてくれた問題。
2次元平面上に、n個のノードがある。このノードは距離d以下の時、直接通信できる。
しかし、今全てのノードが壊れていて動かない。順次修理していくとき、修理されたものを経由してあるノードからあるノードにたどり着く経路が存在するかどうかを答えるというような問題。
union-findでunitするときの動作を勘違いしていて、何で間違うんだろうかと頭を悩ませていました。
むしろ、なんでhttp://d.hatena.ne.jp/atetubou/20110322/1300744974が通ったのか不思議なくらいです。
vectorやcinを使ったらTLEだったので、多少高速化させました。
int G[1001][1001]; int Gs[1001]; ll x[1001],y[1001]; bool rep[1001]; int un[1001]; void init(int n){rep(i,n)un[i]=i;}; int find(int x){ if(x==un[x])return x; else un[x]=find(un[x]); } void unit(int a,int b){ un[find(a)]=un[find(b)]=find(a); } main(){ ll n,d; cin>>n>>d; init(n); rep(i,n)scanf("%d%d",x+i,y+i); rep(i,n){ rep(j,i){ ll xk=x[j]-x[i],yk=y[j]-y[i]; ll len=xk*xk+yk*yk; if(len>d*d)continue; G[i][Gs[i]++]=j; G[j][Gs[j]++]=i; } } char c; while(cin>>c){ if(c=='O'){ int a; cin>>a; --a; rep[a]=true; rep(i,Gs[a]) if(rep[G[a][i]])unit(a,G[a][i]); }else{ int a,b; cin>>a>>b; --a,--b; if(rep[a] && rep[b] && find(a)==find(b))cout<<"SUCCESS"<<endl; else cout<<"FAIL"<<endl; } } }