답안 #678368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678368 2023-01-05T16:18:27 Z Cyanmond Paint (COI20_paint) C++17
100 / 100
871 ms 251352 KB
#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' : ' ');
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 16 ms 4132 KB Output is correct
4 Correct 27 ms 9044 KB Output is correct
5 Correct 21 ms 10068 KB Output is correct
6 Correct 16 ms 8916 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 17404 KB Output is correct
2 Correct 321 ms 200728 KB Output is correct
3 Correct 286 ms 70980 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 110996 KB Output is correct
2 Correct 354 ms 108732 KB Output is correct
3 Correct 387 ms 147432 KB Output is correct
4 Correct 511 ms 249700 KB Output is correct
5 Correct 440 ms 221804 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 70232 KB Output is correct
2 Correct 465 ms 88876 KB Output is correct
3 Correct 846 ms 235288 KB Output is correct
4 Correct 871 ms 251352 KB Output is correct
5 Correct 870 ms 132652 KB Output is correct
6 Correct 419 ms 223820 KB Output is correct
7 Correct 352 ms 171792 KB Output is correct
8 Correct 324 ms 132960 KB Output is correct
9 Correct 769 ms 88604 KB Output is correct