Submission #1305902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305902		NikoBaotic	Paint (COI20_paint)	C++20	100 / 100	303 ms	87700 KiB

paint

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 2e5 + 10;
const int K = 1e3;
const int C = 1e5 + 10;
const int B = N / K + 10;

const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int n, m, q;
int c[N];
int sz[N];
int par[N];
int bigInd[N];
int vis[N];
int du[N];
int cur = 1;
int br = 1;

vector<int> vel[N];
vector<vector<int>> s[B];

int conv(int x, int y) {
	return x * m + y;
}

int find(int a) {
	if (par[a] == a) return a;
	return par[a] = find(par[a]);
}

void dfs(int x, int y, int v, vector<int>& ans) {
	vis[conv(x, y)] = v;

	for (int k = 0; k < 4; k++) {
		int nx = x + dir[k][0];
		int ny = y + dir[k][1];

		if (nx < 0 or ny < 0 or nx >= n or ny >= m) continue;
		if (vis[conv(nx, ny)] == v) continue;

		if (find(conv(x, y)) == find(conv(nx, ny))) {
			dfs(nx, ny, v, ans);
		} else {
			ans.pb(find(conv(nx, ny)));
		}
	}
}

vector<int> getSus(int ind) {
	ind = find(ind);

	int x = ind / m;
	int y = ind % m;

	vector<int> ans;

	dfs(x, y, br++, ans);

	vector<int> de;

	du[ind] = br;

	for (int k : ans) {
		if (du[k] == br) continue;
		du[k] = br;
		de.pb(k);
	}

	br++;
	
	return de;
}

void evolve(int ind) {
	ind = find(ind);
	bigInd[ind] = cur++;

	vector<int> sus = getSus(ind);

	s[bigInd[ind]] = vector<vector<int>>(C, vector<int>());

	for (int x : sus) {
		vel[find(x)].pb(ind);
		s[bigInd[ind]][c[find(x)]].pb(find(x));
	}
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b) return;

	if (sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];

	for (int x : vel[a]) {
		du[x] = br;
	}

	for (int x : vel[b]) {
		if (du[x] == br) continue;
		du[x] = br;

		vel[a].pb(x);
	}

	br++;

	if (sz[a] > K and bigInd[a] == 0) {
		par[b] = a;
		evolve(a);
	} else if (bigInd[a]) {
		vector<int> sus = getSus(b);

		for (int x : sus) {
			if (find(x) == a) continue;

			vel[find(x)].pb(a);
			s[bigInd[a]][c[find(x)]].pb(find(x));
		}

		par[b] = a;
	} else {
		par[b] = a;
	}
}

void paint(int a, int col) {
	a = find(a);

	if (bigInd[a] == 0) {
		vector<int> sus = getSus(a);

		for (int x : sus) {
			if (c[find(x)] == col) {
				merge(a, x);
				c[find(a)] = col;
			}
		}
	} else {
		for (int x : s[bigInd[a]][col]) {
			if (c[find(x)] == col) {
				merge(a, x);
				c[find(a)] = col;
			}
		}

		s[bigInd[a]][col].clear();

		for (int x : vel[a]) {
			if (c[find(x)] == col) {
				merge(a, x);
				c[find(a)] = col;
			}
		}
	}

	for (int x : vel[a]) {
		if (find(x) == find(a)) continue;

		s[bigInd[find(x)]][col].pb(find(a));
	}

	a = find(a);
	c[a] = col;
}

int main() {
	FIO;
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c[conv(i, j)];
		}
	}

	for (int i = 0; i < N; i++) {
		sz[i] = 1;
		par[i] = i;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				int nx = i + dir[k][0];
				int ny = j + dir[k][1];

				if (nx < 0 or ny < 0 or nx >= n or ny >= m) continue;

				if (c[find(conv(i, j))] == c[find(conv(nx, ny))]) {
					merge(conv(i, j), conv(nx, ny));
				}
			}
		}
	}

	cin >> q;

	while (q--) {
		int x, y, z;
		cin >> x >> y >> z;

		paint(conv(x - 1, y - 1), z);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << c[find(conv(i, j))] << " ";
		}
		cout << endl;
	}

	return 0;
}

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