Submission #577001

#	Time	Username	Problem	Language	Result	Execution time	Memory
577001		penguinhacker	Paint (COI20_paint)	C++17	100 / 100	625 ms	72524 KiB

paint

#include <bits/stdc++.h>
using namespace std;

#define ar array
const int mxN=2e5, B=700; // 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 sz, color;
	bool large;
	set<int> small_neighbors, big_neighbors;
	unordered_map<int, set<int>> by_color;
} components[mxN];

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

void declare_large(int u) {
	components[u].large=1;
	for (int v : components[u].small_neighbors) {
		components[u].by_color[components[v].color].insert(v);
		components[v].big_neighbors.insert(u);
	}
	set<int>().swap(components[u].small_neighbors);
}

void mrg(int u, int v) {
	int color=components[u].color;
	if (components[u].sz<components[v].sz)
		swap(u, v);
	if (components[u].sz+components[v].sz>=B) { // new component is large, merge them
		if (!components[u].large)
			declare_large(u);
		if (!components[v].large)
			declare_large(v);
		for (int rep=0; rep<2; ++rep) {
			auto it=components[u].by_color.find(color);
			auto it2=it->second.find(v);
			it->second.erase(it2);
			if (it->second.empty())
				components[u].by_color.erase(color);
			swap(u, v);
		}
		for (auto& x : components[v].by_color) // move by_color
			for (int y : x.second) {
				if (components[y].large) {
					components[y].by_color[color].erase(v);
					components[y].by_color[color].insert(u);
				} else {
					components[y].small_neighbors.erase(v);
					components[y].small_neighbors.insert(u);
				}
				components[y].big_neighbors.erase(v);
				components[y].big_neighbors.insert(u);

				components[u].by_color[x.first].insert(y);
			}
		unordered_map<int, set<int>>().swap(components[v].by_color);
	} else { // both are still small
		for (int rep=0; rep<2; ++rep) {
			auto it=components[u].small_neighbors.find(v);
			components[u].small_neighbors.erase(it);
			swap(u, v);
		}
		for (int x : components[v].small_neighbors) {
			if (components[x].large) {
				components[x].by_color[color].erase(v);
				components[x].by_color[color].insert(u);
			} else {
				components[x].small_neighbors.erase(v);
				components[x].small_neighbors.insert(u);
			}
			components[u].small_neighbors.insert(x);
		}
		set<int>().swap(components[v].small_neighbors);
	}

	p[v]=u;
	for (int x : components[v].big_neighbors)
		components[u].big_neighbors.insert(x);
	set<int>().swap(components[v].big_neighbors);
	components[u].big_neighbors.erase(u);
	components[u].big_neighbors.erase(v);
}

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;
			int sz=0;
			while(q.size()) {
				int i=q.front()[0], j=q.front()[1];
				q.pop();
				++sz;
				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].sz=sz;
			components[cc].color=grid[i][j];
			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.insert(vis[i+1][j]);
				components[vis[i+1][j]].small_neighbors.insert(vis[i][j]);
			}
			if (j+1<m&&grid[i][j]!=grid[i][j+1]) {
				components[vis[i][j]].small_neighbors.insert(vis[i][j+1]);
				components[vis[i][j+1]].small_neighbors.insert(vis[i][j]);
			}
		}
	for (int i=0; i<cc; ++i)
		if (components[i].sz>=B)
			declare_large(i);
	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
		int last_color=components[u].color;
		components[u].color=c;
		for (int v : components[u].big_neighbors) { // they need to know that color of this component has changed
			components[v].by_color[last_color].erase(u);
			if (components[v].by_color[last_color].empty())
				components[v].by_color.erase(last_color);
			components[v].by_color[c].insert(u);
		}
		vector<int> cands;
		if (!components[u].large) { // small
			for (int i : components[u].small_neighbors)
				cands.push_back(i);
		} else {
			if (components[u].by_color.find(c)!=components[u].by_color.end())
				for (int i : components[u].by_color[c])
					cands.push_back(i);
		}
		for (int v : cands) {
			if (find(v)!=u&&components[find(v)].color==c) {
				mrg(u, find(v));
				u=find(u);
			}
		}
	}
	for (int i=0; i<n; ++i) {
		for (int j=0; j<m; ++j)
			cout << components[find(vis[i][j])].color << " ";
		cout << "\n";
	}
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 31 / 31
• Subtask 4: 52 / 52