Submission #678368

#	Time	Username	Problem	Language	Result	Execution time	Memory
678368		Cyanmond	Paint (COI20_paint)	C++17	100 / 100	871 ms	251352 KiB

paint

#include <bits/stdc++.h>

constexpr std::array<std::pair<int, int>, 4> dxy = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};

constexpr int B = 1000, H = 100000;

struct UnionFind {
    int n;
    std::vector<int> tree, color;

    UnionFind(int n_) {
        n = n_;
        tree.assign(n, -1);
        color.assign(n, 0);
    }

    int find(int v) {
        if (tree[v] < 0) {
            return v;
        } else {
            return tree[v] = find(tree[v]);
        }
    }

    int size(int v) {
        return -tree[find(v)];
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (size(a) < size(b)) {
            std::swap(a, b);
        }

        tree[a] += tree[b];
        tree[b] = a;
    }

    int get_color(int v) {
        return color[find(v)];
    }

    void set_color(int v, int c) {
        color[find(v)] = c;
    }
};

int main() {
    int R, S;
    std::cin >> R >> S;
    std::vector<std::vector<int>> C(R, std::vector<int>(S));
    for (auto &vec : C) {
        for (auto &e : vec) {
            std::cin >> e;
        }
    }

    int Q;
    std::cin >> Q;
    std::vector<int> r(Q), s(Q), c(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> r[i] >> s[i] >> c[i];
        --r[i], --s[i];
    }

    auto get_id = [&](int x, int y) {
        return x * S + y;
    };

    UnionFind uft(R * S);
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < S; ++j) {
            uft.set_color(get_id(i, j), C[i][j]);
            for (const auto &[ax, ay] : dxy) {
                const int nx = i + ax, ny = j + ay;
                if (nx < 0 or ny < 0 or nx >= R or ny >= S) {
                    continue;
                }
                if (C[i][j] == C[nx][ny]) {
                    uft.unite(get_id(i, j), get_id(nx, ny));
                }
            }
        }
    }

    std::vector<std::unordered_set<int>> graph(R * S);
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < S; ++j) {
            for (const auto &[ax, ay] : dxy) {
                const int nx = i + ax, ny = j + ay;
                if (nx < 0 or ny < 0 or nx >= R or ny >= S) {
                    continue;
                }
                if (C[i][j] != C[nx][ny]) {
                    graph[uft.find(get_id(i, j))].insert(uft.find(get_id(nx, ny)));
                }
            }
        }
    }

    std::vector<std::vector<std::unordered_set<int>>> gb(R * S);
    std::vector<std::unordered_set<int>> large_list(R * S);
    for (int i = 0; i < R * S; ++i) {
        if (uft.find(i) == i and uft.size(i) >= B) {
            gb[i].resize(H);
            for (const int t : graph[i]) {
                large_list[t].insert(i);
                gb[i][uft.get_color(t)].insert(t);
            }
        }
    }

    auto inc_block = [&](int v) {
        assert(uft.size(v) >= B);
        gb[v].resize(H);
        for (const int t : graph[v]) {
            large_list[uft.find(t)].insert(v);
            gb[v][uft.get_color(t)].insert(uft.find(t));
        }
    };

    auto merge_large = [&](int a, int b) {
        if (uft.size(a) < uft.size(b)) {
            std::swap(a, b);
        }
        if (uft.size(b) < B) {
            for (const int t : graph[b]) {
                const int v = uft.find(t);
                gb[a][uft.get_color(v)].insert(v);
                large_list[uft.find(t)].insert(a);
            }
        } else {
            for (int i = 0; i < H; ++i) {
                for (const int e : gb[b][i]) {
                    gb[a][i].insert(uft.find(e));
                }
            }
        }
        uft.unite(a, b);

        for (const int e : large_list[b]) {
            large_list[a].insert(uft.find(e));
        }
    };

    auto merge_small = [&](int a, int b) {
        if (uft.size(a) < uft.size(b)) {
            std::swap(a, b);
        }
        uft.unite(a, b);
        for (const int e : graph[b]) {
            graph[a].insert(uft.find(e));
        }
        for (const int e : large_list[b]) {
            large_list[a].insert(uft.find(e));
        }

        if (uft.size(a) >= B) {
            inc_block(a);
        }
    };

    auto merge = [&](int a, int b) {
        a = uft.find(a);
        b = uft.find(b);
        if (a == b) {
            return;
        }
        if (std::max(uft.size(a), uft.size(b)) >= B) {
            merge_large(a, b);
        } else {
            merge_small(a, b);
        }
    };

    for (int i = 0; i < Q; ++i) {
        const int x = r[i], y = s[i];
        const int v = uft.find(get_id(x, y));
        uft.set_color(v, c[i]);
        if (uft.size(v) >= B) {
            auto g = gb[v][c[i]];
            gb[v][c[i]].clear();
            for (const int t : g) {
                if (uft.get_color(t) != c[i]) {
                    continue;
                }
                if (uft.find(v) == uft.find(t)) {
                    continue;
                } else {
                    merge(v, t);
                }
            }
        } else {
            auto cp = graph[v];
            for (const int t : cp) {
                if (uft.get_color(t) == c[i] and uft.find(v) != uft.find(t)) {
                    merge(v, t);
                }
            }
        }

        for (const int t : large_list[uft.find(v)]) {
            gb[uft.find(t)][uft.get_color(v)].insert(uft.find(v));
        }
    }

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < S; ++j) {
            std::cout << uft.get_color(get_id(i, j)) << (j == S - 1 ? '\n' : ' ');
        }
    }
}

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