oj.uz

답안 #576306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
576306 2022-06-13T02:08:33 Z penguinhacker Paint (COI20_paint) C++14
8 / 100
 3000 ms 51356 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
const int mxN=2e5, B=400; // component is considered large if size>=B
const int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};

int p[mxN];
struct Component {
	int color;
	bool large;
	vector<ar<int, 2>> pixels;
	vector<int> small_neighbors, big_neighbors;
	map<int, vector<int>> by_color;
	int size() {
		return pixels.size();
	}
} components[mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

void declare_large(int u) {
	assert(u==find(u)&&!components[u].large);
	components[u].large=1;
	for (int i : components[u].small_neighbors) {
		int v=find(i);
		components[u].by_color[components[v].color].push_back(v);
		components[v].big_neighbors.push_back(u);
	}
	vector<int>().swap(components[u].small_neighbors);
}

void mrg(int u, int v) {
	//cout << u << " " << v << endl;
	assert(u==find(u)&&v==find(v)&&components[u].color==components[v].color);
	if (components[u].size()<components[v].size())
		swap(u, v);
	assert(components[u].large>=components[v].large);

	components[u].pixels.insert(components[u].pixels.end(), components[v].pixels.begin(), components[v].pixels.end()); // move pixels
	vector<ar<int, 2>>().swap(components[v].pixels);

	components[u].big_neighbors.insert(components[u].big_neighbors.end(), components[v].big_neighbors.begin(), components[v].big_neighbors.end()); // move big_neighbors
	vector<int>().swap(components[v].big_neighbors);

	if (components[u].size()+components[v].size()>=B) { // new component is large, merge them
		if (!components[u].large)
			declare_large(u);
		if (!components[v].large)
			declare_large(v);
		for (auto& x : components[v].by_color) // move by_color
			for (int y : x.second)
				components[u].by_color[x.first].push_back(y);
		map<int, vector<int>>().swap(components[v].by_color);
	} else { // both are still small
		components[u].small_neighbors.insert(components[u].small_neighbors.end(), components[v].small_neighbors.begin(), components[v].small_neighbors.end()); // move small_neighbors
		vector<int>().swap(components[v].small_neighbors);
	}
	p[v]=u;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> grid(n, vector<int>(m));
	for (vector<int>& v : grid)
		for (int& i : v)
			cin >> i;
	vector<vector<int>> vis(n, vector<int>(m, -1));
	int cc=0; // component counter
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j) {
			if (vis[i][j]!=-1)
				continue;
			queue<ar<int, 2>> q;
			q.push({i, j});
			vis[i][j]=cc;
			vector<ar<int, 2>> pixels;
			while(q.size()) {
				int i=q.front()[0], j=q.front()[1];
				q.pop();
				pixels.push_back({i, j});
				for (int k=0; k<4; ++k) {
					int ni=i+dx[k], nj=j+dy[k];
					if (0<=ni&&ni<n&&0<=nj&&nj<m&&vis[ni][nj]==-1&&grid[i][j]==grid[ni][nj]) {
						q.push({ni, nj});
						vis[ni][nj]=cc;
					}
				}
			}
			components[cc].color=grid[i][j];
			components[cc].pixels=pixels;
			p[cc]=cc;
			++cc;
		}
	for (int i=0; i<n; ++i) {
		for (int j=0; j<m; ++j) {
			if (i+1<n&&grid[i][j]!=grid[i+1][j]) {
				components[vis[i][j]].small_neighbors.push_back(vis[i+1][j]);
				components[vis[i+1][j]].small_neighbors.push_back(vis[i][j]);
			}
			if (j+1<m&&grid[i][j]!=grid[i][j+1]) {
				components[vis[i][j]].small_neighbors.push_back(vis[i][j+1]);
				components[vis[i][j+1]].small_neighbors.push_back(vis[i][j]);
			}
			//cout << vis[i][j] << " ";
		}
		//cout << endl;
	}
	for (int i=0; i<cc; ++i) {
		vector<int>& v=components[i].small_neighbors;
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end())-v.begin());
		/*cout << i << " :";
		for (int j : v)
			cout << " " << j;
		cout << endl;*/
	}
	for (int i=0; i<cc; ++i)
		if (components[i].size()>=B)
			declare_large(i);
	//cout << "REACHED" << endl;
	int q;
	cin >> q;
	while(q--) {
		int i, j, c;
		cin >> i >> j >> c, --i, --j;
		int u=find(vis[i][j]); // what is the actual component
		components[u].color=c;
		for (int v : components[u].big_neighbors) // they need to know that color of this component has changed
			components[find(v)].by_color[c].push_back(u);

		vector<int> cands=components[u].large?components[u].by_color[c]:components[u].small_neighbors;
		for (int v : cands)
			if (find(v)!=u&&components[find(v)].color==c) {
				mrg(u, find(v));
				u=find(u);
			}
		if (components[u].large)
			components[u].by_color.erase(c);
	}
	vector<vector<int>> ans(n, vector<int>(m));
	for (int i=0; i<cc; ++i)
		if (i==find(i))
			for (ar<int, 2> x : components[i].pixels)
				ans[x[0]][x[1]]=components[i].color;
	for (int i=0; i<n; ++i) {
		for (int j=0; j<m; ++j)
			cout << ans[i][j] << " ";
		cout << "\n";
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 25428 KB Output is correct
2 Correct 17 ms 25448 KB Output is correct
3 Correct 18 ms 26288 KB Output is correct
4 Correct 20 ms 26196 KB Output is correct
5 Correct 336 ms 26896 KB Output is correct
6 Correct 749 ms 26288 KB Output is correct
7 Correct 14 ms 25300 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 29596 KB Output is correct
2 Correct 238 ms 33948 KB Output is correct
3 Execution timed out 3070 ms 36580 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3059 ms 51356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 39968 KB Output is correct
2 Execution timed out 3076 ms 46940 KB Time limit exceeded
3 Halted 0 ms 0 KB -