Submission #1176909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176909		1bin	Paint (COI20_paint)	C++20	0 / 100	49 ms	24648 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 = 300;
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;
vector<int> adj[NMAX];
set<int> B;
map<int, set<int>> mp[NMAX];
vector<vector<int>> A, vis;
vector<pair<int, 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);
    par[b] = a;
    mp[a][C[b]].erase(b);
    if (sz[a] > sqt && sz[b] > sqt) {   // Big + Big
        mp[b][C[a]].erase(a);
        for (auto&[c, v] : mp[b])
            for (auto x : v) mp[a][c].emplace(find(x));
        B.erase(b);
    }
    else if (sz[a] > sqt && sz[b] < sqt) {   // Big + Small
        for (int x : adj[b]) {
            x = find(x);
            if (x != a) mp[a][C[x]].emplace(x);
        }
    }
    else {// Small + Small
        for (int x : adj[b]) {
            x = find(x);
            if (x != a) adj[a].emplace_back(x);
        }
        if (sz[a] + sz[b] > sqt) {
            for (int x : adj[a]) {
                x = find(x);
                mp[a][C[x]].emplace(x);
            }
            B.emplace(a);
        }
    }
    sz[a] += sz[b];
}

void update() {
    for (auto& x : B) {
        for (auto[c, y] : modified)
            if (mp[x][c].find(y) != mp[x][c].end()) {
                mp[x][c].erase(y);
                y = find(y);
                mp[x][C[y]].emplace(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_back(find(ni));
            }
    for (int i = 0; i < n * m; i++)
        if (i == find(i) && sz[i] > sqt) {
            B.emplace(i);
            for (int& y : adj[i]) mp[i][C[y]].emplace(y);
        }

    cin >> Q;
    while (Q--) {
        cin >> y >> x >> c; y--; x--;
        int i = find(y * m + x);
        int bc = C[i];
        modified.emplace_back(bc, i);

        if (sz[i] <= sqt) {
            for (int ni : adj[i]) {
                ni = find(ni);
                if (C[ni] == c) {
                    modified.emplace_back(c, ni);
                    unite(i, ni);
                    if (sz[find(i)] > sqt) break;
                }
            }
        }
        if (sz[i] > sqt) {
            auto v = mp[i][c];
            for (auto x : v) {
                modified.emplace_back(c, x);
                unite(i, x);
            }
        }
        C[i] = c;
        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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52