Submission #1192198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192198		nhq0914	Paint (COI20_paint)	C++17	100 / 100	252 ms	50528 KiB

paint

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define N(a) (int)a.size()
#define pb push_back
#define FO(i, a, b) for(int i = (a); i <= (b); ++i)
#define RE(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;

const int nn = 2e5 + 1, sr = 448;

int n, m, q, a[nn], rt[nn];
bool is_heavy[nn];

vector <int> adj[nn], to_add;
vector <pair <int, int>> to_add_pairs;
set <int> heavy[nn];
set <pair <int, int>> light[nn];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int get(int v) {return v == rt[v] ? v : rt[v] = get(rt[v]);}

void join(int u, int v) {
	if((u = get(u)) == (v = get(v))) return;
	
	if(N(adj[u]) < N(adj[v])) swap(u, v);
	if(N(light[u]) < N(light[v])) light[u].swap(light[v]);
	if(N(heavy[u]) < N(heavy[v])) heavy[u].swap(heavy[v]);

	for(int &x: adj[v]) {
		x = get(x);
		if(is_heavy[x]) {
			if(is_heavy[u]) heavy[u].insert(x), heavy[x].insert(u);
			else light[x].insert({a[u], u});
		}
		else if(is_heavy[u]) light[u].insert({a[x], x});
		adj[u].pb(x);
	}

	for(int x: heavy[v]) heavy[u].insert(x);
	for(pair <int, int> x: light[v]) light[u].insert(x);

	rt[v] = u;

	if(!is_heavy[u] && N(adj[u]) > sr) {
		is_heavy[u] = true;
		for(int &x: adj[u]) {
			x = get(x);
			if(x == u) continue;
			light[u].insert({a[x], x});
			if(is_heavy[x]) heavy[u].insert(x), heavy[x].insert(u);
		}
	}
}

int main() {
	cin.tie(0);
	ios :: sync_with_stdio(0);

	cin >> n >> m;
	FO(i, 0, n - 1) FO(j, 0, m - 1) cin >> a[i * m + j];
	FO(i, 0, n - 1) FO(j, 0, m - 1) {
		rt[i * m + j] = i * m + j;
		FO(k, 0, 3) {
			int x = i + dx[k], y = j + dy[k];
			if(x < 0 || y < 0 || x >= n || y >= m) continue;
			if(a[i * m + j] == a[x * m + y]) to_add_pairs.pb({i * m + j, x * m + y});
			else adj[i * m + j].push_back(x * m + y);
		}
	}
	for(pair <int, int> &x: to_add_pairs) join(x.first, x.second);
	cin >> q;
	for(int x, y, c; q--;) {
		cin >> x >> y >> c;
		--x, --y;
		int r = get(x * m + y);
		a[r] = c;
		to_add.clear();
		if(is_heavy[r]) {
			for(int x: heavy[r]) {
				x = get(x);
				if(r != x && a[r] == a[x]) to_add.pb(x);
			}
			{
				set <pair <int, int>> :: iterator it;
				while(true) {
					it = light[r].lower_bound(make_pair(a[r], -1));
					if(it == light[r].end()) break;
					int x = get(it -> second);
					if(it -> first != a[r]) break;
					if(a[x] == a[r]) to_add.pb(x);
					light[r].erase(it);
				}
			}
		}
		else {
			for(int &x: adj[r]) {
				x = get(x);
				if(x != r && a[x] == a[r]) to_add.pb(x);
				if(is_heavy[x]) light[x].insert({a[r], r});
			}
		}
		for(int &x: to_add) join(r, x);
	}
	FO(i, 0, n - 1) {
		FO(j, 0, m - 1) cout << a[get(i * m + j)] << ' ';
		cout << '\n';
	}

	return 0;
}

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