oj.uz

Submission #420663

# Submission time Handle Problem Language Result Execution time Memory
420663 2021-06-08T13:13:24 Z two_sides Paint (COI20_paint) C++17
0 / 100
 155 ms 59936 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;
const int MAXC = 100005;
const size_t MAXS = 400;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};


int N, M;
bool vis[MAXN];

#define valid(x, y) (x) >= 0 && (x) < N && (y) >= 0 && (y) < M
#define flat(x, y) (x) * M + y
#define comps(x, y) comps[flat(x, y)]

struct component {
    int col, idx;
    vector <int> big;
    vector <vector <int>> grp;
    vector <pair <int, int>> cell;
} comps[MAXN];

int getCol(int u) {
    return comps[comps[u].idx].col;
}

int getCol(int x, int y) {
    return getCol(flat(x, y));
}

vector <int> get(const component &a, int col) {
    static int x, y;
    static vector <int> res;

    if (a.cell.size() >= MAXS)
        return a.grp[col];
    res.clear();
    if (col) {
        for (auto pp : a.cell) {
            tie(x, y) = pp;
            for (int k = 0; k < 4; k++)
                if (valid(x + dx[k], y + dy[k]) &&
                getCol(x + dx[k], y + dy[k]) == col)
                    res.push_back(comps(x + dx[k], y + dy[k]).idx);
        }
    } else {
        for (auto pp : a.cell) {
            tie(x, y) = pp;
            for (int k = 0; k < 4; k++)
                if (valid(x + dx[k], y + dy[k]) &&
                getCol(x + dx[k], y + dy[k]) != a.col)
                    res.push_back(comps(x + dx[k], y + dy[k]).idx);
        }
    }
    return res;
}

bool join(int u, int v) {
    static vector <int> tmp;

    u = comps[u].idx; v = comps[v].idx;
    if (u == v) return false;
    if (comps[u].cell.size() < comps[v].cell.size())
        swap(u, v);
    component &a = comps[u];
    component &b = comps[v];
    for (auto pp : b.cell) {
        a.cell.push_back(pp);
        comps(pp.first, pp.second).idx = u;
    }
    for (auto x : b.big) {
        a.big.push_back(x);
        comps[comps[x].idx].grp[a.col].push_back(u);
    }
    if (a.cell.size() < MAXS) {
        if (a.cell.size() + b.cell.size() >= MAXS) {
            tmp = get(a, 0);
            a.grp.resize(MAXC);
            for (int x : tmp) {
                a.grp[comps[x].col].push_back(x);
                comps[x].big.push_back(u);
            }
            tmp = get(b, 0);
            for (int x : tmp) {
                a.grp[comps[x].col].push_back(x);
                comps[x].big.push_back(u);
            }
        }
    } else if (b.cell.size() < MAXS) {
        tmp = get(b, 0);
        for (int x : tmp) {
            a.grp[comps[x].col].push_back(x);
            comps[x].big.push_back(u);
        }
    } else {
        for (int c = 1; c < MAXC; c++) {
            if (a.grp[c].size() < b.grp[c].size())
                swap(a.grp[c], b.grp[c]);
            for (int x : b.grp[c])
                a.grp[c].push_back(x);
            
        }
    }
    return true;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M;
    vector <vector <int>> S(N, vector <int> (M));
    for (int i = 0; i < N; i++)
        for (int j = 0;  j < M; j++)
            cin >> S[i][j];
    queue <pair <int, int>> que;
    vector <int> big;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (vis[flat(i, j)]) continue;
            que.emplace(i, j); int x, y;
            vis[flat(i, j)] = true;
            comps(i, j).col = S[i][j] + 1;
            while (que.size()) {
                tie(x, y) = que.front(); que.pop();
                comps(i, j).cell.emplace_back(x, y);
                comps(x, y).idx = flat(i, j);
                for (int k = 0; k < 4; k++)
                    if (valid(x + dx[k], y + dy[k]) &&
                    !vis[flat(x + dx[k], y + dy[k])] &&
                    S[x + dx[k]][y + dy[k]] == S[i][j]) {
                        vis[flat(x + dx[k], y + dy[k])] = true;
                        que.emplace(x + dx[k], y + dy[k]);
                    }
            }
            if (comps(i, j).cell.size() >= MAXS)
                big.push_back(flat(i, j));
        }
    for (int u : big) {
        vector <int> neighbor; int x, y;
        for (auto pp : comps[u].cell) {
            tie(x, y) = pp;
            for (int k = 0; k < 4; k++)
                if (valid(x + dx[k], y + dy[k]) &&
                getCol(x + dx[k], y + dy[k]) != comps[u].col)
                    neighbor.push_back(comps(x + dx[k], y + dy[k]).idx);
        }
        comps[u].grp.resize(MAXC);
        for (int x : neighbor) {
            comps[u].grp[comps[x].col].push_back(x);
            comps[x].big.push_back(u);
        }
    }
    int Q; cin >> Q;
    while (Q--) {
        int x, y, col; cin >> x >> y >> col;
        x--; y--; col++;
        int u = comps(x, y).idx;
        if (col == comps[u].col) continue;
        comps[u].col = col;
        vector <int> neighbor = get(comps[u], col);
        for (int v : neighbor) join(u, v);
    }
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cout << getCol(i, j) - 1 << " \n"[j == M - 1];

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 9 ms 15980 KB Output is correct
3 Correct 15 ms 16332 KB Output is correct
4 Incorrect 18 ms 18752 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18076 KB Output is correct
2 Runtime error 155 ms 59936 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 52500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 42452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -