Submission #1176831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176831		1bin	Paint (COI20_paint)	C++20	0 / 100	3095 ms	18964 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[NMAX], Y[NMAX], x, y, c;
set<int> B;
map<int, set<int>> mp[NMAX];
vector<vector<int>> ix, vis;
vector<pair<int, int>> modified;
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

vector<int> find_adj (int sy, int sx){
    queue<pair<int, int>> q, tmp;
    vector<int> adj;
    q.emplace(sy, sx); vis[sy][sx] = 1;
    int i = find(ix[sy][sx]);

    while (q.size()) {
        auto[y, x] = q.front(); q.pop();
        tmp.emplace(y, x);
        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 || vis[ny][nx]) continue;
            int ni = find(ix[ny][nx]);
            if (i == ni) {
                q.emplace(ny, nx); vis[ny][nx] = 1;
            }
            else adj.emplace_back(ni);
        }
    }
    sort(all(adj));
    adj.erase(unique(all(adj)), adj.end());

    while (tmp.size()) {
        auto[y, x] = tmp.front(); tmp.pop();
        vis[y][x] = 0;
    }
    return adj;
}

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(x);
        B.erase(b);
    }
    else if (sz[a] > sqt && sz[b] < sqt) {   // Big + Small
        auto adj = find_adj(Y[b], X[b]);
        for (int x : adj)
            if (x != a) mp[a][C[x]].emplace(x);
    }
    else if (sz[a] + sz[b] > sqt) { // Small + Small
        auto adj = find_adj(Y[a], Y[b]);
        for (int x : adj) mp[a][C[x]].emplace(x);
        B.emplace(a);
    }
    sz[a] += sz[b];
}

void bfs(int i, int c) {
    auto adj = find_adj(Y[i], X[i]);
    for (int ni : adj)
        if (C[ni] == c) {
            modified.emplace_back(c, ni);
            unite(ni, i);
        }
}

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();
}

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

    memset(par, -1, sizeof(par));
    fill(sz, sz + NMAX, 1);
    cin >> n >> m;
    ix.resize(n); vis.resize(n);
    for (int i = 0; i < n; i++) ix[i].resize(m), vis[i].resize(m);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            ix[i][j] = i * m + j;
            Y[ix[i][j]] = i; X[ix[i][j]] = j;
            cin >> C[ix[i][j]];
            if (i && C[ix[i][j]] == C[ix[i - 1][j]]) unite(ix[i][j], ix[i - 1][j]);
            if (j && C[ix[i][j]] == C[ix[i][j - 1]]) unite(ix[i][j], ix[i][j - 1]);
        }

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

        if (sz[i] <= sqt) bfs(i, c);
        else {
            auto v = mp[i][c];
            for (auto x : v) {
                modified.emplace_back(c, i);
                unite(i, x);
            }
        }
        C[i] = c;
        update();

    }

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

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