oj.uz

Submission #456376

# Submission time Handle Problem Language Result Execution time Memory
456376 2021-08-06T14:53:38 Z grt Paint (COI20_paint) C++17
31 / 100
 325 ms 78684 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14668 KB Output is correct
2 Correct 10 ms 14796 KB Output is correct
3 Incorrect 21 ms 20164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 32764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 60764 KB Output is correct
2 Correct 263 ms 60516 KB Output is correct
3 Correct 268 ms 60748 KB Output is correct
4 Correct 302 ms 60116 KB Output is correct
5 Correct 262 ms 58224 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 325 ms 78684 KB Output isn't correct
2 Halted 0 ms 0 KB -