AOJ 2235
Graph Construction。かなり一般化された問題。平方分割とUnionFindまでは自明に思い浮かぶとして、実装も軽いので投げれば通る。ちなみにUnionFindのオーダーはランクのほうをつかってO(log n)にしないといけないと思います。経路圧縮をするともとに戻せなくなる。
Scootalooとsqrtって似てると思います。
#include<stdio.h> #include<algorithm> #include<set> using namespace std; int UF[40000]; int BF[40000]; int SCOOT=200; int chg[400000]; int siz; int FIND(int a){ if(UF[a]<0)return a; return FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a); b=FIND(b); if(a==b)return; if(UF[a]>UF[b])swap(a,b); chg[siz++]=a; chg[siz++]=b; UF[a]+=UF[b]; UF[b]=a; } int x[40000]; int y[40000]; int z[40000]; set<pair<int,int> >S; set<pair<int,int> >T; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ scanf("%d%d%d",x+i,y+i,z+i); } for(int i=0;i<a;i++)UF[i]=BF[i]=-1; for(int i=0;i<b;i++){ if(i%SCOOT==0){ T.clear(); for(int j=0;j<SCOOT&&i+j<b;j++){ if(x[i+j]!=3){ T.insert(make_pair(y[i+j],z[i+j])); if(x[i+j]==1)S.insert(make_pair(y[i+j],z[i+j])); if(x[i+j]==2)S.erase(make_pair(y[i+j],z[i+j])); } } for(int j=0;j<a;j++)UF[j]=BF[j]=-1; siz=0; set<pair<int,int> >::iterator it=S.begin(); while(it!=S.end()){ pair<int,int>W=*it; // if(i==9000){ // printf("%d %d\n",W.first,W.second); // fflush(stdout); // } if(!T.count(W))UNION(W.first,W.second); it++; } for(int j=0;j<a;j++)BF[j]=UF[j]; } if(x[i]==3){ set<pair<int,int> >U; int n=i/SCOOT*SCOOT; for(int j=0;j<i%SCOOT;j++){ if(x[n+j]==1)U.insert(make_pair(y[n+j],z[n+j])); if(x[n+j]==2)U.erase(make_pair(y[n+j],z[n+j])); } for(int j=min(SCOOT-1,b-n-1);j>i%SCOOT;j--){ if(x[n+j]==2)U.insert(make_pair(y[n+j],z[n+j])); if(x[n+j]==1)U.erase(make_pair(y[n+j],z[n+j])); } set<pair<int,int> >::iterator it=U.begin(); siz=0; while(it!=U.end()){ pair<int,int>W=*it; UNION(W.first,W.second); it++; } if(FIND(y[i])==FIND(z[i]))printf("YES\n"); else printf("NO\n"); for(int j=0;j<siz;j++)UF[chg[j]]=BF[chg[j]]; } } }
難易度表の750初ACだけど、まあこれはJOIer向けなので…