Submission #420926

#	Time	Username	Problem	Language	Result	Execution time	Memory
420926		phathnv	Paint (COI20_paint)	C++11	48 / 100	3098 ms	60028 KiB

paint

#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 = 666;

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);
    set<int> newAdj;
    for (int v : adj[u]) {
        v = dsu.findRoot(v);
        newAdj.insert(v);
        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[u] = newAdj;
}

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);
    for (auto p : s[v])
        s[u].insert(p);
    adj[v].clear();
    s[v].clear();
    dsu.unite(u, v);
    set<int> newAdj;
    for (int v : adj[u]) {
        v = dsu.findRoot(v);
        if (u == v)
            continue;
        if (dsu.GetSz(u) >= BLOCKSIZE) {
            if (dsu.GetSz(v) >= BLOCKSIZE)
                newAdj.insert(dsu.findRoot(v));
            else
                s[u].insert({dsu.GetCol(v), v});
        } else {
            newAdj.insert(dsu.findRoot(v));
        }
        if (!(dsu.GetSz(v) >= BLOCKSIZE && dsu.GetSz(u) < BLOCKSIZE))
            adj[v].insert(u);
    }
    adj[u] = newAdj;
    if (dsu.GetSz(u) < BLOCKSIZE)
        Update(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]]);
                    adj[u].insert(v);
                    adj[v].insert(u);
                }
    for (int u = 0; u < m * n; u++)
        if (dsu.findRoot(u) == u) {
            if (dsu.GetSz(u) < BLOCKSIZE) {
                Update(u, 1);
            } else {
                set<int> newAdj;
                for(int x : adj[u])
                    if (dsu.GetSz(x) >= BLOCKSIZE)
                        newAdj.insert(x);
                adj[u] = newAdj;
            }
        }
    cin >> q;
    while (q--) {
        int x, y, c;
        cin >> x >> y >> c;
        x--, y--;
        int u = dsu.findRoot(ind[x][y]);
        if (dsu.GetSz(u) < BLOCKSIZE)
            Update(u, -1);
        dsu.SetCol(u, c);
        if (dsu.GetSz(u) < BLOCKSIZE)
            Update(u, 1);
        vector<int> shouldMerge;
        vector<pair<int, int>> shouldDel;
        auto it = s[u].lower_bound({c, 0});
        while (it != s[u].end())
            if ((*it).first == c) {
                shouldMerge.push_back((*it).second);
                shouldDel.push_back((*it));
                ++it;
            } else {
                break;
            }
        for(auto p : shouldDel)
            s[u].erase(p);
        set<int> newAdj;
        for (int v : adj[u]) {
            v = dsu.findRoot(v);
            newAdj.insert(v);
            if (dsu.GetCol(v) == c)
                shouldMerge.push_back(v);
        }
        adj[u] = newAdj;
        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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 31 / 31
• Subtask 4: 0 / 52