Submission #363725

#	Time	Username	Problem	Language	Result	Execution time	Memory
363725		penguinhacker	Paint (COI20_paint)	C++14	100 / 100	981 ms	39080 KiB

paint

// source: https://oj.uz/problem/view/COI20_paint
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 300000;
const int K = 350;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

vector<vector<int>> grid;
vector<vector<bool>> vis;
vector<vector<int>> comp_id;
int comp_vis[mxN];
int comp_tracker = 0;

int n, m;
struct Component {
	int id;
	int color;
	bool large;
	vector<pair<int, int>> pixels;
	vector<int> larges;
	map<int, vector<int>> by_color;
};
vector<Component> C;
int parent[mxN];

int get_par(int id) {
	return id == parent[id] ? id : parent[id] = get_par(parent[id]);
}

void trav_neighbors(int id, function<void(int)> f) {
	++comp_tracker;
	for (pair<int, int> cell : C[id].pixels) {
		for (int k = 0; k < 4; ++k) {
			int a = cell.first + dx[k];
			int b = cell.second + dy[k];
			if (a < 0 || a >= n || b < 0 || b >= m) continue;
			int nid = comp_id[a][b];
			if (id != nid && comp_vis[nid] != comp_tracker) {
				comp_vis[nid] = comp_tracker;
				f(nid);
			}
		}
	}
}

vector<int> get_neighbors(int id, int color) {
	vector<int> ret;
	Component& comp = C[id];
	if (comp.large) {
		++comp_tracker;
		for (int x : comp.by_color[color]) {
			int nid = get_par(x);
			if (id != nid && comp_vis[nid] != comp_tracker && C[nid].color == color) {
				comp_vis[nid] = comp_tracker;
				ret.push_back(nid);
			}
		}
		comp.by_color.erase(color); // save memory
	}
	else {
		trav_neighbors(id, [&ret, color](int nid) {
			if (color == C[nid].color) ret.push_back(nid);
		});
	}
	return ret;
}

void declare_large(int id) {
	C[id].large = 1;
	trav_neighbors(id, [id](int nid) {
		C[nid].larges.push_back(id);
		C[id].by_color[C[nid].color].push_back(nid);
	});
}

void trav_larges(int id, function<void(int)> f) {
	++comp_tracker;
	for (int x : C[id].larges) {
		int nid = get_par(x);
		if (id != nid && comp_vis[nid] != comp_tracker) {
			comp_vis[nid] = comp_tracker;
			f(nid);
		}
	}
}

void remake_larges(int id) {
	vector<int> new_larges;
	trav_larges(id, [&new_larges](int nid) {
		new_larges.push_back(nid);
	});
	C[id].larges.swap(new_larges);
}

int Merge(int a, int b) { // merge b into a
	assert(a != b);
	if (C[a].pixels.size() < C[b].pixels.size()) swap(a, b);
	if (C[a].large && !C[b].large) declare_large(b);

	parent[b] = a;
	for (pair<int, int> x : C[b].pixels) {
		comp_id[x.first][x.second] = a;
		C[a].pixels.push_back(x);
	}
	vector<pair<int, int>>().swap(C[b].pixels);

	if (C[a].larges.size() < C[b].larges.size()) swap(C[a].larges, C[b].larges);
	for (int x : C[b].larges) C[a].larges.push_back(x);
	vector<int>().swap(C[b].larges);
	remake_larges(a);

	if (C[a].by_color.size() < C[b].by_color.size()) swap(C[a].by_color, C[b].by_color);
	for (auto& entry : C[b].by_color) {
		int color = entry.first;
		vector<int>& lista = C[a].by_color[color];
		vector<int>& listb = entry.second;
		if (lista.size() < listb.size()) swap(lista, listb);
		for (int x : listb) lista.push_back(x);
	}
	map<int, vector<int>>().swap(C[b].by_color);
	
	if (!C[a].large && C[a].pixels.size() > K) {
		declare_large(a);
	}
	//cerr << "successfully merged " << a << " and " << b << "\n";
	return a;
}

void fill(int i, int j, int color) {
	int id = comp_id[i][j];
	C[id].color = color;
	for (int nid : get_neighbors(id, color)) {
		id = Merge(id, nid);
	}
	trav_larges(id, [id, color](int nid) {
		C[nid].by_color[color].push_back(id);
	});
}

/////////////////////////////////// Some initialization

vector<pair<int, int>> traversal;
void dfs_for_component(int i, int j) {
	vis[i][j] = 1;
	comp_id[i][j] = C.size();
	traversal.emplace_back(i, j);
	for (int k = 0; k < 4; ++k) {
		int a = i + dx[k];
		int b = j + dy[k];
		if (0 <= a && a < n && 0 <= b && b < m && !vis[a][b] && grid[i][j] == grid[a][b]) {
			dfs_for_component(a, b);
		}
	}
}

void init() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (vis[i][j]) continue;
			Component cur;
			dfs_for_component(i, j);
			cur.id = C.size();
			cur.color = grid[i][j];
			cur.large = 0;
			swap(traversal, cur.pixels);
			C.push_back(cur);
		}
	}
	for (Component& c : C) {
		if (c.pixels.size() > K) {
			declare_large(c.id);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	grid = vector<vector<int>>(n, vector<int>(m));
	vis = vector<vector<bool>>(n, vector<bool>(m));
	comp_id = vector<vector<int>>(n, vector<int>(m));
	iota(parent, parent + n * m, 0);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> grid[i][j];
		}
	}
	init();
	//cerr << "Reached\n";
	int q; cin >> q;
	while(q--) {
		int i, j, color; cin >> i >> j >> color, --i, --j;
		fill(i, j, color);
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (j) cout << " ";
			cout << C[comp_id[i][j]].color;
		}
		cout << "\n";
	}
	return 0;
}

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