Submission #420513

#	Time	Username	Problem	Language	Result	Execution time	Memory
420513		phathnv	Paint (COI20_paint)	C++11	8 / 100	3099 ms	68532 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 = 88888;

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(v), v});
        } else {
            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)});
    }
    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]) {
            //cerr << v << ' ' << dsu.GetCol(v) << endl;
            if (dsu.GetCol(v) == c)
                shouldMerge.push_back(v);
        }
//        cerr << "shouldMerge: ";
//        for(int x : shouldMerge)
//            cerr << x << ' ';
//        cerr << endl;
        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++)
//                cerr << dsu.GetCol(ind[i][j]) << ' ';
//            cerr << '\n';
//        }
//        cerr << endl;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            cout << dsu.GetCol(ind[i][j]) << ' ';
        cout << '\n';
    }
    return 0;
}

/*
1 3
1 2 1
1
1 2 1


1 3
1 2 1
2
1 2 1
1 3 3
*/

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