Submission #420597

# Submission time Handle Problem Language Result Execution time Memory
420597 2021-06-08T12:53:51 Z phathnv Paint (COI20_paint) C++11
0 / 100
2 ms 388 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[dsu.findRoot(v)].insert({dsu.GetCol(u), u});
        } else {
            s[dsu.findRoot(v)].erase({dsu.GetCol(u), 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)});
        adj[u] = newAdj;
    } else if (dsu.GetSz(u) < BLOCKSIZE) {
        Update(u, 1);
    }
}

int main() {
    freopen("inp.txt", "r", stdin);
    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 (dsu.GetSz(u) < 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]);
        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);
        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;
}

Compilation message

paint.cpp: In function 'int main()':
paint.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     freopen("inp.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -