oj.uz

Submission #393421

# Submission time Handle Problem Language Result Execution time Memory
393421 2021-04-23T12:01:59 Z VEGAnn Paint (COI20_paint) C++14
100 / 100
 682 ms 60364 KB 
#include <bits/stdc++.h>
#define ft first
#define sd second
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
const int N = 200100;
const int BLOCK = 400;

vector<i2> elms;
bool init_mrk[N];
int n, m, pre[N];
int c[N], who[N];

int used[N], tt = 0;
int stp[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

struct comp{
    int color;
    vector<i2> pnts;
    vector<int> big_neib;
    bool large;
    map<int, vector<int> > by_color;
};

vector<comp> comps;

int get_pre(int x) { return (pre[x] == x ? x : pre[x] = get_pre(pre[x])); }

void init_dfs(int x, int y, int now){
    if (x < 0 || y < 0 || x >= n || y >= m) return;
    if (init_mrk[x * m + y]) return;
    if (c[x * m + y] != now) return;

    elms.PB({x, y});
    init_mrk[x * m + y] = 1;
    who[x * m + y] = sz(comps);

    for (int it = 0; it < 4; it++){
        int cx = x + stp[it][0];
        int cy = y + stp[it][1];

        init_dfs(cx, cy, now);
    }
}

void declare_big(comp &now){
    now.large = 1;

    tt++;

    for (i2 CR : now.pnts){
        int x = CR[0], y = CR[1];

        int cur_comp = who[x * m + y];

        for (int it = 0; it < 4; it++){
            int cx = x + stp[it][0];
            int cy = y + stp[it][1];

            if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;

            int co_id = who[cx * m + cy];

            if (used[co_id] < tt){
                used[co_id] = tt;
                comps[co_id].big_neib.PB(cur_comp);
                comps[cur_comp].by_color[comps[co_id].color].PB(co_id);
            }
        }
    }
}

void Init(){
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> c[i * m + j];

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        if (init_mrk[i * m + j]) continue;

        elms.clear();

        init_dfs(i, j, c[i * m + j]);

        comp new_comp;

        new_comp.color = c[i * m + j];
        new_comp.pnts = elms;
        new_comp.large = 0;

        new_comp.big_neib.clear();
        new_comp.by_color.clear();

        comps.PB(new_comp);
    }

    for (int i = 0; i < n * m; i++)
        pre[i] = i;

    for (int i = 0; i < sz(comps); i++)
        if (sz(comps[i].pnts) > BLOCK)
            declare_big(comps[i]);
}

void merge(int c1, int c2){
    c1 = get_pre(c1);
    c2 = get_pre(c2);

    assert(c1 != c2);

    if (sz(comps[c1].pnts) < sz(comps[c2].pnts))
        swap(c1, c2);

    comp &fi = comps[c1];
    comp &se = comps[c2];

    if (fi.large && !se.large)
        declare_big(se);

    if (se.large && !fi.large)
        declare_big(fi);

    {
        /// update pnts

        pre[c2] = c1;

        for (i2 CR : se.pnts){
            int x = CR[0], y = CR[1];

            fi.pnts.PB(CR);
            who[x * m + y] = c1;
        }

        vector<i2> ().swap(se.pnts);
    }

    {
        /// update big_neib

        vector<int> nw_big;

        nw_big.clear();

        tt++;

        for (int cr : fi.big_neib){
            cr = get_pre(cr);

            if (used[cr] < tt) {
                nw_big.PB(cr);
                used[cr] = tt;
            }
        }

        for (int cr : se.big_neib){
            cr = get_pre(cr);

            if (used[cr] < tt) {
                nw_big.PB(cr);
                used[cr] = tt;
            }
        }

        vector<int> ().swap(fi.big_neib);
        vector<int> ().swap(se.big_neib);

        fi.big_neib.swap(nw_big);
    }

    if (fi.large) {
        /// update by_color

        if (sz(fi.by_color) < sz(se.by_color))
            fi.by_color.swap(se.by_color);

        for (auto cr : se.by_color){
            int col = cr.ft;
            vector<int> &sml = cr.sd;
            vector<int> &big = fi.by_color[col];

            if (sz(sml) > sz(big))
                sml.swap(big);

            for (int cr : sml)
                big.PB(cr);

            vector<int> ().swap(sml);
        }
    }

    if (!fi.large && sz(fi.pnts) > BLOCK)
        declare_big(fi);
}

void Fill(int x, int y, int nw_col){
    int cur_comp = who[x * m + y];

    comps[cur_comp].color = nw_col;

    if (comps[cur_comp].large){
        tt++;

        vector<int> nw;
        nw.clear();

        used[cur_comp] = tt;

        vector<int> &CUR = comps[cur_comp].by_color[nw_col];

        for (int it = 0; it < sz(CUR); it++){
            int co_id = CUR[it];

            co_id = get_pre(co_id);

            if (used[co_id] < tt && comps[co_id].color == nw_col){
                nw.PB(co_id);
                used[co_id] = tt;
            } else {
                swap(CUR[it], CUR.back());
                CUR.pop_back();
                it--;
            }
        }

        for (int ids : nw)
            merge(cur_comp, ids);
    } else {
        tt++;

        vector<int> nw;
        nw.clear();

        used[cur_comp] = tt;

        for (i2 CR : comps[cur_comp].pnts){
            int X = CR[0], Y = CR[1];

            for (int it = 0; it < 4; it++){
                int cx = X + stp[it][0];
                int cy = Y + stp[it][1];

                if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;

                int co_id = who[cx * m + cy];

                if (used[co_id] < tt && comps[co_id].color == nw_col){
                    nw.PB(co_id);
                    used[co_id] = tt;
                }
            }
        }

        for (int ids : nw)
            merge(cur_comp, ids);
    }

    /// traverse big_neib and change color

    cur_comp = who[x * m + y];

    int col = comps[cur_comp].color;

    tt++;

    used[cur_comp] = tt;

    for (int cr : comps[cur_comp].big_neib){
        cr = get_pre(cr);

        if (used[cr] < tt) {
            comps[cr].by_color[col].PB(cur_comp);
            used[cr] = tt;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    Init();

    int qq; cin >> qq;

    for (; qq; qq--){
        int x, y, col; cin >> x >> y >> col; x--; y--;

        if (qq % 10000 == 0)
            cerr << qq << '\n';

        Fill(x, y, col);
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            int co_id = who[i * m + j];

            cout << comps[co_id].color << " ";
        }
        cout << '\n';
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 6 ms 2404 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 12 ms 2400 KB Output is correct
6 Correct 10 ms 1620 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8836 KB Output is correct
2 Correct 126 ms 17624 KB Output is correct
3 Correct 252 ms 49412 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 60364 KB Output is correct
2 Correct 221 ms 47732 KB Output is correct
3 Correct 251 ms 57488 KB Output is correct
4 Correct 274 ms 44736 KB Output is correct
5 Correct 225 ms 42512 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 27280 KB Output is correct
2 Correct 499 ms 40700 KB Output is correct
3 Correct 651 ms 58632 KB Output is correct
4 Correct 524 ms 55724 KB Output is correct
5 Correct 643 ms 48876 KB Output is correct
6 Correct 187 ms 31260 KB Output is correct
7 Correct 201 ms 27312 KB Output is correct
8 Correct 178 ms 24420 KB Output is correct
9 Correct 682 ms 48616 KB Output is correct