Submission #926443

#	Time	Username	Problem	Language	Result	Execution time	Memory
926443		NK_	Paint (COI20_paint)	C++17	100 / 100	473 ms	64188 KiB

paint

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;

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

const int SQ = 500; // determines what is heavy and what is light

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N, M; cin >> N >> M;

	// auto P = [&](int x) {
	// 	return "{ " + to_string(x / M) + " " + to_string(x % M) + " }";
	// };

	V<vi> A(N, vi(M)); for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
		cin >> A[r][c];
	}

	vi ID(N * M), C(N * M), H(N * M, 0); V<vi> E(N * M); V<set<int>> EH(N * M); V<set<pi>> L(N * M);
	// L -> adj to the set (color, vertex)

	
	vpi CMB;
	for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
		ID[r * M + c] = r * M + c;

		for(int d = 0; d < 4; d++) {
			int nr = r + dx[d], nc = c + dy[d];
			if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;

			E[r * M + c].pb(nr * M + nc); // add edge between adj. cells
			if (A[r][c] == A[nr][nc]) CMB.pb(mp(r * M + c, nr * M + nc));
		}

		C[r * M + c] = A[r][c];
	}

	function<int(int)> get = [&](int u) {
		return ID[u] == u ? u : ID[u] = get(ID[u]); 
	};

	auto merge = [&](int u, int v) {
		// cout << u / M << " " << u % M << " <= U => " << v / M << " " << v % M << endl;

		u = get(u), v = get(v);
		if (u == v) return;

		if (sz(E[u]) < sz(E[v])) swap(u, v);
		if (sz(EH[u]) < sz(EH[v])) EH[u].swap(EH[v]);
		if (sz(L[u]) < sz(L[v])) L[u].swap(L[v]);

		for(auto x : E[v]) {
			x = get(x);

			if (H[x]) { // is hvy
				// L[x].erase(mp(C[v], v));
				if (H[u]) {
					EH[x].insert(u);
					EH[u].insert(x);
				} else L[x].insert(mp(C[u], u));
			} else { // is light
				if (H[u]) L[u].insert(mp(C[x], x));
			}
			E[u].pb(x);	
		}

		for(auto& x : EH[v]) EH[u].insert(get(x));
		for(auto& x : L[v]) L[u].insert(x);

		ID[v] = u;

		if (!H[u] && sz(E[u]) > SQ) {
			H[u] = 1;
			for(auto x : E[u]) {
				int r = get(x);
				if (r == u) continue;

				L[u].insert(mp(C[r], r)); 

				if (H[r]) { // is hvy => hvy together
					EH[r].insert(u);
					EH[u].insert(r);
				}
			}
		}
	};

	auto print = [&]() {
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < M; c++) {
				int u = r * M + c; cout << C[get(u)] << " ";
			}
			cout << nl;
		}
	};

	
	for(auto& p : CMB) {
		auto [u, v] = p;
		merge(u, v);
	}

	// for(int r = 0; r < N; r++) {
	// 	cout << "--------------------------------" << nl;
	// 	for(int c = 0; c < M; c++) {
	// 		int u = r * M + c; cout << P(get(u)) << " | ";
	// 	}
	// 	cout << nl;
	// }
					
	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int r, c, s; cin >> r >> c >> s; --r, --c;
		// if (i % 100 == 0) cout << i << endl;
		int u = r * M + c; u = get(u); 

		// s stores the old color
		swap(C[u], s);

		vi cmb;
		if (H[u]) { // if heavy:

			// go through heavy nodes -> N / B
			for(auto& v : EH[u]) {
				int rx = get(v);
				// cout << P(u) << " <= HH => " << P(rx) << nl;
				if (rx != u && C[rx] == C[u]) cmb.pb(rx);
			}

			// go through light nodes -> log(N)
			{
				while(1) {
					auto it = L[u].lower_bound(mp(C[u], -1));
					if (it == end(L[u])) break;
					auto [cv, v] = *it;
					v = get(v);
					if (cv == C[u]) {
						if (C[v] == C[u]) cmb.pb(v); 
						L[u].erase(it);
					} else break;
				}
			}

		} else { // if light: 

			// go through all adjacent -> B * log(N)
			for(auto& v : E[u]) {
				int rx = get(v);
				if (rx != u && C[rx] == C[u]) cmb.pb(rx);
				if (H[rx]) { // is hvy
					// L[rx].erase(mp(s, u));
					L[rx].insert(mp(C[u], u));
				}
			}	
		}

		for(auto& x : cmb) merge(u, x);

		// print();
	}	


	// after updates find the adjacents with the same color
	// two parts -> color and adjacent
	// can store either color or adjacent 
	// how do you check whether adjacent with a color?
	// with adjacent you have to find color efficiently
	// if you store (color, vertex) pair in a set, then you can find the adjacents quickly
	// you also have to update them
	// SQRT Decomp? but its N * sqrt(N) * log(N)?
	// Light -> B * log(N) + (N / B), heavy -> N / B + log(N)

	print();

	exit(0-0);
}

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