Codeforces ECR #031 : E. Binary Matrix

うーむ、本番解けず。
http://codeforces.com/contest/884/problem/E

問題

N*Mのグリッドが与えられる。
各セルには0か1の値が埋められている。

1が埋められた隣接セル同士の連結関係を考えるとき、連結成分はいくつあるか。

なお、この問題はメモリ上限がN*Mより小さい。

解法

メモリが多ければ、Union-FindなりDFSなりで解けるが、今回はそうはいかない。
そこで、上から連続する２行ずつ見ていって、その間でのみUnion-Findで連結していこう。

1が埋まったセル数から、異なる成分を連結した回数の分を引けば求める数が得られる。

template<int um> class UF {
	public:
	vector<int> par;
	UF() {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) {
		x=operator[](x);
		y=operator[](y);
		return par[x]=par[y]=max(x,y);
	}
};
UF<1<<15> uf;

int H,W;

string S;
bitset<1<<14> A,B;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	int V=0;
	
	FOR(y,H) {
		FOR(x,W) if(A[x]) uf.par[x]=uf[x+W]-W;
		FOR(x,W) uf.par[x+W]=x+W;
		cin>>S;
		FORR(c,S) {
			if(c>='0' && c<='9') c-='0';
			else c=c-'A'+10;
		}
		FOR(x,W) {
			if(S[x/4]&(1<<(3-x%4))) {
				V++;
				B[x]=1;
				if(A[x]&&uf[x]!=uf[x+W]) V--, uf(x,x+W);
			}
			else B[x]=0;
		}
		FOR(x,W-1) {
			if(B[x]&&B[x+1]&&uf[x+W]!=uf[x+W+1]) {
				V--;
				uf(x+W,x+W+1);
			}
		}
		
		A=B;
	}
	
	cout<<V<<endl;
	
}

まとめ

Union-Findっぽい感じでマージしていくことは考えたのに、なぜUnion-Find自体を使おうとしなかったのか…。