yukicoder : No.307 最近色塗る問題多くない？

意外に時間制限が厳しい？
http://yukicoder.me/problems/769

問題

H*Wのグリッドがある。
初期状態で各セルは2色のどちらかで塗られている。

ここでQ個のクエリが与えられる。
各クエリでは、あるセル及び同色の隣接マスを介して隣接するセル群を、指定された色で塗る。

全クエリ終了後、各セルの色を答えよ。

解法

Union-Findを用いて連結セル群を管理しつつ、連結セル群に隣接する逆の色のセルの集合を更新していくと良い。

クエリの際、各セルを元と同じ色で塗る場合、そのクエリは無視してよい。
元のセルと逆の色で塗る場合、今度は「連結セル群に隣接する逆の色のセル」とすべて連結させていこう。

連結セル群に隣接する逆の色のセルの集合の管理は、適当にsetを用いるとTLEする。
マージテク等を使い値のコピーを減らすか、vector+sort+unique等で処理を軽くした方がよい。

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;

int H,W,Q;
int A[201*201];
vector<int> S[201*201];
int id(int y,int x){ return y*W+x;}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>A[id(y,x)];
	}
	FOR(y,H) FOR(x,W) {
		if(y) {
			if(A[id(y,x)]==A[id(y-1,x)]) uf(id(y,x),id(y-1,x));
			else S[id(y,x)].push_back(id(y-1,x));
		}
		if(y<H-1) {
			if(A[id(y,x)]==A[id(y+1,x)]) uf(id(y,x),id(y+1,x));
			else S[id(y,x)].push_back(id(y+1,x));
		}
		if(x) {
			if(A[id(y,x)]==A[id(y,x-1)]) uf(id(y,x),id(y,x-1));
			else S[id(y,x)].push_back(id(y,x-1));
		}
		if(x<W-1) {
			if(A[id(y,x)]==A[id(y,x+1)]) uf(id(y,x),id(y,x+1));
			else S[id(y,x)].push_back(id(y,x+1));
		}
	}
	
	FOR(x,H*W) if(uf[x]!=x) FORR(r,S[x]) S[uf[x]].push_back(r);
	FOR(x,H*W) if(uf[x]==x) {
		sort(ALL(S[x]));
		S[x].erase(unique(ALL(S[x])),S[x].end());
	}
	cin>>Q;
	while(Q--) {
		cin>>y>>x>>k;
		x=uf[id(y-1,x-1)];
		if(A[x]==k) continue;
		
		vector<int> NEW;
		FORR(r,S[x]) if(uf[x]!=uf[r]) {
			FORR(r2,S[uf[r]]) if(uf[r2]!=uf[x]) NEW.push_back(uf[r2]);
			uf(x,r);
		}
		sort(ALL(NEW));
		NEW.erase(unique(ALL(NEW)),NEW.end());
		
		S[uf[x]]=NEW;
		A[uf[x]]=k;
	}
	
	FOR(y,H) FOR(x,W) _P("%d%c",A[uf[id(y,x)]],(x==W-1)?'\n':' ');
	
}

まとめ

yukicoderの色塗り問題、実装重いの多いよね。