oj.uz

답안 #420531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420531 2021-06-08T12:23:15 Z phathnv Paint (COI20_paint) C++11
0 / 100
 3000 ms 82728 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> root, col, sz;
    void init(int n) {
        root.assign(n, 0);
        col.assign(n, 0);
        sz.assign(n, 1);
        iota(root.begin(), root.end(), 0);
    }
    int findRoot(int u) {
        if (u == root[u])
            return u;
        return root[u] = findRoot(root[u]);
    }
    void SetCol(int u, int c) {
        col[findRoot(u)] = c;
    }
    int GetCol(int u) {
        return col[findRoot(u)];
    }
    int GetSz(int u) {
        return sz[findRoot(u)];
    }
    void unite(int u, int v) {
        u = findRoot(u);
        v = findRoot(v);
        assert(col[u] == col[v]);
        if (u == v)
            return;
        if (sz[u] < sz[v])
            swap(u, v);
        root[v] = u;
        sz[u] += sz[v];
    }
};

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
const int BLOCKSIZE = 888;

int m, n, q, curInd;
vector<vector<int>> a, ind;
vector<set<int>> adj;
vector<set<pair<int, int>>> s;
DSU dsu;

void Update(int u, int type) {
    assert(dsu.GetSz(u) < BLOCKSIZE);
    u = dsu.findRoot(u);
    for (int v : adj[u]) {
        if (dsu.GetSz(v) < BLOCKSIZE)
            continue;
        if (type == 1) {
            s[v].insert({dsu.GetCol(u), u});
        } else {
            s[v].erase({dsu.GetCol(u), u});
            adj[v].erase(u);
        }
    }
}

void Merge(int u, int v) {
    u = dsu.findRoot(u);
    v = dsu.findRoot(v);
    if (u == v)
        return;
    if (dsu.GetSz(u) < dsu.GetSz(v))
        swap(u, v);
    if (dsu.GetSz(u) < BLOCKSIZE)
        Update(u, -1);
    if (dsu.GetSz(v) < BLOCKSIZE)
        Update(v, -1);
    for (int x : adj[v]) {
        adj[u].insert(x);
        if (dsu.GetSz(u) >= BLOCKSIZE && dsu.GetSz(x) < BLOCKSIZE)
            s[u].insert({dsu.GetCol(x), dsu.findRoot(x)});
    }
    for (auto p : s[v])
        s[u].insert(p);
    s[v].clear();
    adj[v].clear();
    int preSz = dsu.GetSz(u);
    dsu.unite(u, v);
    adj[v].clear();
    if (preSz < BLOCKSIZE && dsu.GetSz(u) >= BLOCKSIZE) {
        set<int> newAdj;
        for (int x : adj[u])
            if (dsu.GetSz(x) >= BLOCKSIZE)
                newAdj.insert(dsu.findRoot(x));
            else
                s[u].insert({dsu.GetCol(x), dsu.findRoot(x)});
    } else if (dsu.GetSz(u) < BLOCKSIZE) {
        Update(dsu.findRoot(u), 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    a.assign(m, vector<int>(n, 0));
    ind.assign(m, vector<int>(n, 0));
    adj.assign(m * n, set<int>());
    s.assign(m * n, set<pair<int, int>>());
    dsu.init(m * n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            ind[i][j] = curInd++;
            dsu.SetCol(ind[i][j], a[i][j]);
        }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            for (int dir = 0; dir < 4; dir++)
                if (0 <= i + dx[dir] && i + dx[dir] < m && 0 <= j + dy[dir] && j + dy[dir] < n && a[i][j] == a[i + dx[dir]][j + dy[dir]])
                    dsu.unite(ind[i][j], ind[i + dx[dir]][j + dy[dir]]);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            for (int dir = 0; dir < 4; dir++)
                if (0 <= i + dx[dir] && i + dx[dir] < m && 0 <= j + dy[dir] && j + dy[dir] < n && a[i][j] != a[i + dx[dir]][j + dy[dir]]) {
                    int u = dsu.findRoot(ind[i][j]), v = dsu.findRoot(ind[i + dx[dir]][j + dy[dir]]);
                    if (dsu.GetSz(u) < BLOCKSIZE || dsu.GetSz(v) >= BLOCKSIZE)
                        adj[u].insert(v);
                    if (dsu.GetSz(v) < BLOCKSIZE || dsu.GetSz(u) >= BLOCKSIZE)
                        adj[v].insert(u);
                }
    for (int u = 0; u < m * n; u++)
        if (dsu.findRoot(u) == u)
            if (adj[u].size() < BLOCKSIZE)
                Update(u, 1);
    cin >> q;
    while (q--) {
        int x, y, c;
        cin >> x >> y >> c;
        x--, y--;
        int u = dsu.findRoot(ind[x][y]);
        dsu.SetCol(u, c);
        vector<int> shouldMerge;
        auto it = s[u].lower_bound({c, 0});
        while (it != s[u].end())
            if ((*it).first == c) {
                shouldMerge.push_back((*it).second);
                ++it;
            } else {
                break;
            }
        for (int v : adj[u])
            if (dsu.GetCol(v) == c)
                shouldMerge.push_back(v);
        for (int v : shouldMerge) {
            Merge(u, v);
            u = dsu.findRoot(u);
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            cout << dsu.GetCol(ind[i][j]) << ' ';
        cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 10 ms 3176 KB Output is correct
4 Correct 24 ms 2612 KB Output is correct
5 Runtime error 6 ms 4044 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 10220 KB Output is correct
2 Runtime error 392 ms 36312 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3061 ms 61128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 296 ms 82728 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -