Submission #926446

#	Time	Username	Problem	Language	Result	Execution time	Memory
926446		NK_	Paint (COI20_paint)	C++17	100 / 100	460 ms	63332 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 = 630; // determines what is heavy and what is light

struct Scanner {
    FILE* stream;
    Scanner(FILE* s) : stream(s) {}
    char buf[1 << 20], * l = buf, * r = buf;
    bool flush() { l = buf; r = l + fread(buf, 1, 1 << 20, stream); return l == r; }
    void get(char& c) { c = l == r && flush() ? ' ' : *l++; }
    friend Scanner& operator >>(Scanner& in, char& c) { return in.get(c), in; }
    friend Scanner& operator >>(Scanner& in, char* s) {
        for (in.get(s[0]); isspace(s[0]); in.get(s[0]));
        for (int i = 0; !isspace(s[i]) || (s[i] = '\0'); i++) in.get(s[i + 1]);
        return in;
    }
    friend Scanner& operator >>(Scanner& in, std::string& s) {
        char c;
        for (in.get(c); isspace(c); in.get(c));
        for (s = ""; !isspace(c); in.get(c)) s += c;
        return in;
    }
    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    friend Scanner& operator >>(Scanner& in, T& x) {
        char c, f = '+';
        for (in.get(c); !isdigit(c); in.get(c))
            if constexpr (std::is_signed_v<T>) f = c;
        for (x = 0; isdigit(c); in.get(c)) x = x * (1 << 1) + x * (1 << 3) + c - '0';
        if constexpr (std::is_signed_v<T>) x = f == '-' ? -x : x;
        return in;
    }
    template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
    friend Scanner& operator >>(Scanner& in, T& x) {
        std::string s; in >> s; x = std::stod(s);
        return in;
    }
    template <class T, class U>
    friend Scanner& operator >>(Scanner& in, std::pair<T, U>& a) {
        return in >> a.first >> a.second;
    }
    template <class T, size_t S>
    friend Scanner& operator >>(Scanner& in, std::array<T, S>& a) {
        for (int i = 0, n = S; i < n; i++) in >> a[i];
        return in;
    }
    template <class T>
    friend Scanner& operator >>(Scanner& in, std::vector<T>& a) {
        for (int i = 0, n = a.size(); i < n; i++) in >> a[i];
        return in;
    }
};
 
struct Printer {
    FILE* stream;
    Printer(FILE* s) : stream(s) {}
    char buf[1 << 20], * l = buf, * r = buf + (1 << 20) - 1;
    int format = 0, precision = 15;
    ~Printer() { flush(); }
    void flush() { fwrite(buf, 1, l - buf, stream); l = buf; }
    void put(const char& c) { *l++ = c; if (l == r) flush(); }
    friend Printer& operator <<(Printer& out, const char& c) { return out.put(c), out; }
    friend Printer& operator <<(Printer& out, const char* s) {
        for (int i = 0; s[i] != '\0'; i++) out.put(s[i]);
        return out;
    }
    friend Printer& operator <<(Printer& out, const std::string& s) {
        for (int i = 0, n = s.size(); i < n; i++) out.put(s[i]);
        return out;
    }
    template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
    friend Printer& operator <<(Printer& out, T x) {
        static char s[40];
        static int i = 0;
        if (x == 0) { out.put('0'); return out; }
        if constexpr (std::is_signed_v<T>) x = x < 0 ? out.put('-'), -x : x;
        while (x > 0) s[++i] = x % 10 + '0', x /= 10;
        while (i > 0) out.put(s[i--]);
        return out;
    }
    template <class T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
    friend Printer& operator <<(Printer& out, T x) {
        std::ostringstream oss;
        oss << std::fixed << std::setprecision(out.precision) << x;
        return out << oss.str();
    }
    template <class T, class U>
    friend Printer& operator <<(Printer& out, const std::pair<T, U>& a) {
        return out << a.first << " \n"[out.format > 1] << a.second;
    }
    template <class T, size_t S>
    friend Printer& operator <<(Printer& out, const std::array<T, S>& a) {
        out << a[0];
        for (int i = 1, n = S; i < n; i++) out << " \n"[out.format > 1] << a[i];
        return out;
    }
    template <class T>
    friend Printer& operator <<(Printer& out, const std::vector<T>& a) {
        if (!a.empty()) out << a[0];
        for (int i = 1, n = a.size(); i < n; i++) out << " \n"[out.format > 0] << a[i];
        return out;
    }
};

Scanner in(stdin);
Printer out(stdout);

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N, M; in >> 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++) {
		in >> 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; out << C[get(u)] << " ";
			}
			out << 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; in >> Q;
	for(int i = 0; i < Q; i++) {
		int r, c, s; in >> 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