oj.uz

Submission #584848

# Submission time Handle Problem Language Result Execution time Memory
584848 2022-06-28T04:54:40 Z eecs Paint (COI20_paint) C++17
100 / 100
 814 ms 456104 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010, B = 500;
int r, c, q, bel[maxn], col[maxn];
vector<int> V[maxn], adj[maxn];
vector<set<int>> S[maxn];
bool mark[maxn];
set<int> big;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> r >> c;
    for (int i = 0; i < r * c; i++) {
        cin >> col[i];
        bel[i] = i, V[i] = {i};
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            for (auto dir : {array<int, 2>{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                int x = i + dir[0], y = j + dir[1];
                if (!~x || x == r || !~y || y == c) continue;
                adj[i * c + j].push_back(x * c + y);
            }
        }
    }
    auto merge = [&](int u, int v) {
        if (V[u].size() < V[v].size()) swap(u, v);
        if (V[u].size() < B && V[u].size() + V[v].size() >= B) {
            S[u].resize(1e5), big.insert(u);
            for (int x : adj[u]) S[u][col[bel[x]]].insert(bel[x]);
        }
        if (V[u].size() + V[v].size() >= B) {
            for (int x : adj[v]) S[u][col[bel[x]]].insert(bel[x]);
            S[v].clear(), S[v].shrink_to_fit(), big.erase(v);
        }
        for (int x : V[v]) bel[x] = u;
        copy(V[v].begin(), V[v].end(), back_inserter(V[u]));
        copy(adj[v].begin(), adj[v].end(), back_inserter(adj[u]));
    };
    auto fill = [&](int u, int x) {
        u = bel[u];
        while (1) {
            if (S[u].size() < B) {
                bool flag = 0;
                auto tmp = adj[u];
                for (int v : tmp) {
                    v = bel[v];
                    if (u ^ v && col[v] == x) merge(u, v), flag = 1, u = bel[u];
                }
                if (!flag) break;
            } else {
                if (S[u][x].empty()) break;
                int v = *S[u][x].begin();
                S[u][x].erase(v), v = bel[v];
                if (u ^ v && col[v] == x) merge(u, v), u = bel[u];
            }
        }
        col[u] = x;
        if (S[u].size() < B) {
            vector<int> _adj;
            for (int v : adj[u]) {
                v = bel[v];
                if (u ^ v && !mark[v]) _adj.push_back(v), mark[v] = 1;
            }
            adj[u] = _adj;
            for (int v : big) {
                if (mark[v]) S[v][col[u]].insert(u);
            }
            for (int v : adj[u]) mark[v] = 0;
        } else {
            for (int v : big) {
                if (u ^ v && S[u][col[v]].count(v)) S[v][col[u]].insert(u);
            }
        }
    };
    for (int i = 0; i < r * c; i++) {
        fill(i, col[i]);
    }
    cin >> q;
    while (q--) {
        int i, j, x;
        cin >> i >> j >> x;
        fill(--i * c + --j, x);
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << col[bel[i * c + j]] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14524 KB Output is correct
3 Correct 15 ms 15156 KB Output is correct
4 Correct 18 ms 19820 KB Output is correct
5 Correct 18 ms 20292 KB Output is correct
6 Correct 34 ms 29492 KB Output is correct
7 Correct 7 ms 14372 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18164 KB Output is correct
2 Correct 242 ms 239460 KB Output is correct
3 Correct 125 ms 36912 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 54792 KB Output is correct
2 Correct 195 ms 56196 KB Output is correct
3 Correct 208 ms 76512 KB Output is correct
4 Correct 300 ms 167340 KB Output is correct
5 Correct 246 ms 175516 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 41420 KB Output is correct
2 Correct 311 ms 45360 KB Output is correct
3 Correct 814 ms 330316 KB Output is correct
4 Correct 649 ms 456104 KB Output is correct
5 Correct 450 ms 173132 KB Output is correct
6 Correct 279 ms 160628 KB Output is correct
7 Correct 236 ms 123476 KB Output is correct
8 Correct 231 ms 95776 KB Output is correct
9 Correct 338 ms 55936 KB Output is correct