結果

問題 No.307 最近色塗る問題多くない？
コンテスト
ユーザー koyumeishi
提出日時 2015-09-21 23:10:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,056 bytes
コンパイル時間 1,253 ms
コンパイル使用メモリ 97,796 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-21 21:43:44
合計ジャッジ時間 16,419 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

class UnionFindTree{
	typedef struct {
		int parent;
		int rank;
	}base_node;
	
	vector<base_node> node;
public:
	UnionFindTree(int n){
		node.resize(n);
		for(int i=0; i<n; i++){
			node[i].parent=i;
			node[i].rank=0;
		}
	}

	int find(int x){
		if(node[x].parent == x) return x;
		else{
			return node[x].parent = find(node[x].parent);
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}

	void unite(int x, int y){
		x = find(node[x].parent);
		y = find(node[y].parent);
		if(x==y) return;
		if(node[x].rank < node[y].rank){
			node[x].parent = y;
		}else if(node[x].rank > node[y].rank){
			node[y].parent = x;
		}else{
			node[x].rank++;
			unite(x,y);
		}
	}
};

int dx[] = {0,0,1,-1,0,0};
int* dy = dx+2;



#include <ctime>


int main(){

	auto start = clock();

	int h,w;
	cin >> h >> w;
	vector<vector<int>> A(h, vector<int>(w));
	
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin >> A[i][j];
		}
	}

	UnionFindTree uft(h*w);
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			for(int k:{0,2}){
				int r = i+dy[k];
				int c = j+dx[k];
				if(r<0 || r>=h || c<0 || c>=w) continue;
				if(A[i][j] == A[r][c]) uft.unite(i*w + j, r*w + c);
			}
		}
	}

	vector<bool> visit(h*w, false);
	vector<vector<int>> adj(h*w);
	for(int i=0; i<h; i++)
	for(int j=0; j<w; j++){
		int root = uft.find(i*w+j);
		if(visit[root]) continue;

		queue<int> q;
		q.push(root);
		visit[root] = true;

		while(q.size()){
			int pos = q.front();
			q.pop();

			int r = pos/w;
			int c = pos%w;

			for(int k=0; k<4; k++){
				int r_ = r+dy[k];
				int c_ = c+dx[k];
				if(r_<0 || r_>=h || c_<0 || c_>=w) continue;
				if(A[r][c] != A[r_][c_]){
					adj[root].push_back(uft.find(r_*w + c_));
				}else if(visit[r_*w + c_]==false){
					visit[r_*w + c_] = true;
					q.push(r_*w + c_);
				}
			}
		}
	}

	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		int r,c,x;
		cin >> r >> c >> x;
		r--; c--;

		int root = uft.find(r*w + c);
		r = root/w; c = root%w;
		if(A[r][c] == x) continue;

		A[r][c] = x;

		vector<int> next_adj;

		for(int j: adj[root]){
			int j_ = uft.find(j);
			for(int k:adj[j_]){
				if(uft.same(k, root)) continue;
				next_adj.push_back(k);
			}
		}

		for(auto j: adj[root]){
			uft.unite(root, j);
		}

		
		for(int j: adj[root]){
			int j_ = uft.find(j);
			adj[j].resize(0);
		}
		adj[root].resize(0);
		

		sort(next_adj.begin(), next_adj.end());
		next_adj.erase( unique(next_adj.begin(), next_adj.end()), next_adj.end());

		root = uft.find(root);
		adj[root].resize(0);
		for(auto j:next_adj){
			if(uft.same(j, root)) continue;
			adj[root].push_back(j);
		}
		swap(next_adj, adj[root]);
	}

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			int parent = uft.find(i*w + j);
			printf("%d%s", A[parent/w][parent%w], (j==w-1)?"\n":" ");
		}
	}


	auto end = clock();
	//cerr << end-start << endl;
	
	return 0;
}
0