Submission #1177293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177293		1bin	Paint (COI20_paint)	C++20	100 / 100	1122 ms	62020 KiB

paint

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
const int sqt = 400;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m, Q, par[NMAX], sz[NMAX], C[NMAX], x, y, c;
set<int> adj[NMAX];
set<int> B;
set<pair<int, int>> mp[NMAX];
vector<vector<int>> A, vis;
vector<int> modified;
int find(int x){return par[x] == x ? x : par[x] = find(par[x]);}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    modified.emplace_back(b);
    par[b] = a;
    if (sz[a] > sqt && sz[b] > sqt) {   // Big + Big
        if (mp[a].find({C[b], b}) != mp[a].end()) mp[a].erase({C[b], b});
        if (mp[b].find({C[a], a}) != mp[b].end()) mp[b].erase({C[a], a});
        for (auto [c,  x] : mp[b]) {
            x = find(x);
            if (x != a && x != b) mp[a].emplace(C[x], x);
        }
        B.erase(b);
    }
    else if (sz[a] > sqt) {   // Big + Small
        if (mp[a].find({C[b], b}) != mp[a].end()) mp[a].erase({C[b], b});
        for (int x : adj[b]) {
            x = find(x);
            if (x != a) mp[a].emplace(C[x], x);
        }
    }
    else {// Small + Small
        set<int> newS;
        for (int x : adj[b]) {
            x = find(x);
            if (x != a && x != b) newS.emplace(x);
        }
        for (int x : adj[a]) {
            x = find(x);
            if (x != a && x != b) newS.emplace(x);
        }
        adj[a] = newS;
        if (sz[a] + sz[b] > sqt) {
            for (int x : adj[a]) mp[a].emplace(C[x], x);
            B.emplace(a);
        }
    }
    sz[a] += sz[b];
}

void update() {
    for (auto& x : B) {
        for (int y : modified)
            if (mp[x].find({C[y], y}) != mp[x].end()) {
                mp[x].erase({C[y], y});
                y = find(y);
                mp[x].emplace(C[y], y);
            }
    }
    modified.clear();
}

void color(int y, int x, int p){
    if (vis[y][x]) return;
    vis[y][x] = 1; par[y * m + x] = p;
    sz[p]++;
    for (int k = 0; k < 4; k++) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m || A[ny][nx] != A[y][x]) continue;
        color(ny, nx, p);
    }
}

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

    cin >> n >> m;
    vis.resize(n); A.resize(n);
    for (int i = 0; i < n; i++) vis[i].resize(m), A[i].resize(m);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> A[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!vis[i][j]) {
                int rt = i * m + j;
                C[rt] = A[i][j];
                color(i, j, rt);
            }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                int ix = i * m + j, ni = ny * m + nx;
                if (find(ix) != find(ni)) adj[find(ix)].emplace(find(ni));
            }
    for (int i = 0; i < n * m; i++)
        if (i == find(i) && sz[i] > sqt) {
            B.emplace(i);
            for (auto& y : adj[i]) mp[i].emplace(C[y], y);
        }

    cin >> Q;
    while (Q--) {
        cin >> y >> x >> c; y--; x--;
        int i = find(y * m + x);
        for (auto& x : B)
            if (mp[x].find({C[i], i}) != mp[x].end()) {
                mp[x].erase({C[i], i});
                mp[x].emplace(c, i);
            }
        C[i] = c;

        if (sz[i] <= sqt) {
            auto v = adj[i];
            for (int ni : v) {
                ni = find(ni);
                if (C[ni] == c) {
                    unite(i, ni);
                    i = find(i);
                    if (sz[i] > sqt) break;
                }
            }
        }

        if (sz[i] > sqt) {
            vector<int> v;
            auto it = mp[i].lower_bound({c, -1});
            while (it != mp[i].end() && it->first == c) {
                v.emplace_back(it->second); it++;
            }
            for (int ni : v) unite(i, ni);
        }
        update();
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cout << C[find(i * m + j)] << ' ';
        cout << '\n';
    }
    return 0;
}

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