こういうの何度か見たので本番4分ぐらいで解いてた。
https://atcoder.jp/contests/abc131/tasks/abc131_f
問題
二次元座標上でN個の格子点が与えられる。
このうち3点が、軸に平行な長方形の3頂点に位置している場合、残り1か所に点を追加する。
これ以上点が増えなくなるまで点を増やすと、最終的に何個増えた状況になるか。
解法
X座標が同じ、またはY座標が同じ点同士をUnion-Findで連結しよう。
連結成分について、そこに登場するX座標・Y座標の組み合わせはすべて最終的に点が埋められるので、各連結成分に現れるユニークなX座標・Y座標の個数を数えて掛け合わせていけばよい。
int N; map<int,int> Xs; map<int,int> Ys; int X[101010],Y[101010]; template<int um> class UF { public: vector<int> par,rank; UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<500000> uf; set<int> PX[101010],PY[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>X[i]>>Y[i]; if(Xs.count(X[i])) uf(i,Xs[X[i]]); Xs[X[i]]=i; if(Ys.count(Y[i])) uf(i,Ys[Y[i]]); Ys[Y[i]]=i; } FOR(i,N) { PX[uf[i]].insert(X[i]); PY[uf[i]].insert(Y[i]); } ll ret=0; FOR(i,N) ret+=1LL*PX[i].size()*PY[i].size(); cout<<ret-N<<endl; }
まとめ
600ptとはいえ既出すぎでは…と思ったけど、ABCなのでってことなのかな。