Submission #456376

#	Time	Username	Problem	Language	Result	Execution time	Memory
456376		grt	Paint (COI20_paint)	C++17	31 / 100	325 ms	78684 KiB

paint

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

int n, m, q;
vector<vi>t;
map<int, vi>nbh[200 * 1000 + 10];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int p[200 * 1000 + 10];
vi occ[200 * 1000 + 10];

void merge(int x, int y) {
	x = p[x]; y = p[y];
	if(x == y) return;
	if((int)occ[x].size() < (int)occ[y].size()) {
		swap(x, y);
	}
	for(int el : occ[y]) {
		occ[x].PB(el);
		p[el] = x;
	}
	occ[y].clear();
	if((int)nbh[x].size() < (int)nbh[y].size()) {
		nbh[x].swap(nbh[y]);
	}
	for(auto &it : nbh[y]) {
		for(int el : it.ND) {
			nbh[x][it.ST].PB(el);
		}	
	}
	nbh[y].clear();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	t.resize(n);
	for(int i = 0; i < n; ++i) {
		t[i].resize(m);
		for(int j = 0; j < m; ++j) {
			cin >> t[i][j];
			p[i * m + j] = i * m + j;
			occ[i * m + j].PB(i * m + j);
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			for(int d = 0; d < 4; ++d) {
				int x = i + dx[d];
				int y = j + dy[d];
				if(x >= 0 && y >= 0 && x < n && y < m) nbh[i * m + j][t[x][y]].PB(p[x * m + y]);
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			while((int)nbh[p[i * m + j]][t[i][j]].size() > 0) {
				int x = nbh[p[i * m + j]][t[i][j]].back();
				nbh[p[i * m + j]][t[i][j]].pop_back();
				merge(x, i * m + j);
			}	
		}
	}
	cin >> q;
	while(q--) {
		int x, y, c;
		cin >> x >> y >> c;
		x--; y--;
		int z = p[x * m + y];
		t[z / m][z % m] = c;
		while((int)nbh[z][c].size() > 0) {
			int el = nbh[z][c].back();
			nbh[z][c].pop_back();
			el = p[el];
			if(t[el / m][el % m] != c) {
				nbh[z][t[el / m][el % m]].PB(el);
				continue;
			}
			merge(el, z);
			z = p[x * m + y];
		}
		z = p[x * m + y];
		t[z / m][z % m] = c;
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			cout << t[p[i * m + j] / m][p[i * m + j] % m] << " ";
		}
		cout << "\n";
	}
	
	
}

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