結果

問題 No.307 最近色塗る問題多くない？
コンテスト
ユーザー 🐬hec
提出日時 2015-11-27 23:45:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 1,377 bytes
コンパイル時間 1,507 ms
コンパイル使用メモリ 171,332 KB
実行使用メモリ 13,412 KB
最終ジャッジ日時 2024-09-14 01:11:12
合計ジャッジ時間 8,564 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include  <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

const int vmax=50010;
int p[vmax];

void init(){rep(i,vmax) p[i]=i;}
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
void unite(int a,int b){a=find(a),b=find(b);p[b]=a;return;}
bool same(int a,int b){return find(a)==find(b);}

int h,w;
int a[vmax];
int di[4]={1,0,-1,0},dj[4]={0,1,0,-1};

set<int> neighbor[vmax];

int main(void){
	init();
	cin >> h >> w;
	rep(i,h)rep(j,w) cin >> a[w*i+j];
	rep(i,h)rep(j,w){
		int idx=w*i+j;
		rep(k,4){
			int ni=i,nj=j;
			ni+=di[k],nj+=dj[k];
			if(ni<0||h<=ni) continue;
			if(nj<0||w<=nj) continue;
			int nidx=w*ni+nj;
			if(a[idx]==a[nidx]) unite(idx,nidx);
		}
	}

	rep(i,h)rep(j,w){
		int idx=find(w*i+j);
		rep(k,4){
			int ni=i,nj=j;
			ni+=di[k],nj+=dj[k];
			if(ni<0||h<=ni) continue;
			if(nj<0||w<=nj) continue;
			int nidx=find(w*ni+nj);
			if(a[idx]!=a[nidx]) neighbor[idx].insert(nidx);
		}
	}

	int q;
	cin >> q;
	rep(loop,q){
		int r,c,x;
		cin >> r >> c >> x;
		r--,c--;
		int idx=find(w*r+c);
		if(a[idx]==x) continue;
		a[idx]=x;	
		set<int> tmp;
		for(auto &nidx:neighbor[idx]){
			unite(idx,nidx);
			for(auto &j:neighbor[nidx]) tmp.insert(j);
			neighbor[idx].erase(nidx);
		}
		neighbor[idx].insert(tmp.begin(),tmp.end());
	}

	rep(i,h){
		rep(j,w) cout << (j?" ":"") << a[find(w*i+j)];
		cout << endl;
	}
	return 0;
}
0