Submission #576522

#	Time	Username	Problem	Language	Result	Execution time	Memory
576522		balbit	Paint (COI20_paint)	C++14	100 / 100	647 ms	28248 KiB

paint

#include <bits/stdc++.h>
//#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;
const int BS = 300;

int color[maxn], sz[maxn],par[maxn];

map<int, set<int> > touch[maxn/BS+3];

int touchpos[maxn];
int TID = 0;
vector<int> here[maxn];
bool adj[maxn/BS+3][maxn/BS+3];
int whose[maxn/BS+3];

int n,m;

inline int getid(int i, int j) {
    return i*m+j;
}

int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
}

int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

inline bool ingrid(int r, int c) {
    return r>=0&&r<n&&c>=0&&c<m;
}

bool tmpseen[maxn];

vector<int> getadj(int x) {
    vector<int> re;
    for (int e : here[x]) {
        int er = e/m, ec = e%m;
        REP(k,4) {
            int tr = er + dx[k], tc = ec + dy[k];
            if (ingrid(tr, tc)) {
                int hi = find(getid(tr,tc));
                if (!tmpseen[hi]) {
                    re.pb(hi); tmpseen[hi] = 1;
                }
            }
        }
    }
    for (int y : re) tmpseen[y] = 0;
    return re;
}

void mrg(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) {
        return;
    }
    assert(color[a] == color[b]);

    if (SZ(here[a]) < SZ(here[b])) swap(a,b);
    // merge b into a
    bool yoink = 0;
    if (SZ(here[a]) >= BS) {
        int tpa = touchpos[a];
        if (SZ(here[b]) >= BS) {
            int tpb = touchpos[b];
            // big - big
            for (auto &e : touch[tpb]) {
                for (int r : e.s) touch[tpa][e.f].insert(r);
            }
            map<int, set<int> > () . swap(touch[tpb]);

            REP(k, TID) {
                if (adj[tpb][k]) adj[tpa][k] = adj[k][tpa] = 1;
            }
//            REP(r, 100002) {
//                touch[tpa][r].insert(touch[tpa][r].end(), ALL(touch[tpb][r]));
//                vector<int>().swap(touch[tpa][r]);
//            }
        }else{
            for (int hi : getadj(b)) {

                if (color[hi] != color[a]) {
                    if (touchpos[hi] != -1) {
                        adj[tpa][touchpos[hi]] = adj[touchpos[hi]][tpa] = 1;
                    }else{
                        touch[tpa][color[hi]].insert(hi);
                    }
                }else {
//                    assert(hi == a || hi == b);
                }
            }
        }

    }else{
        yoink = 1;
    }
    here[a].insert(here[a].end(), ALL(here[b]));
    par[b] = a;
    if (yoink && SZ(here[a]) >= BS) {
        // upgrade it
        whose[TID] = a;
        int tpa = touchpos[a] = TID++;
        for (int e : getadj(a)) {
            if (color[e] != color[a]) {
                if (touchpos[e] != -1) {
                    adj[tpa][touchpos[e]] = adj[touchpos[e]][tpa] = 1;
                }else{
                    touch[tpa][color[e]].insert(e);
                }
            }else{
//                assert(e == a);
            }
        }
    }
}

void go(int id, int col) {

    id = find(id);

    int r = id/m, c = id%m;

    color[id] = col;
    vector<int> tomerge;

    if (SZ(here[id]) >= BS) {
        // yarrr i'm biggg

        int tp = touchpos[id];
        vector<int> todo;
        if (touch[tp].count(col)) for (int hm : touch[tp][col]) {
            int hh = find(hm);
            if (hh != id && color[hh] == col) {
                if (!tmpseen[hh]) tomerge.pb(hh), tmpseen[hh] = 1;
            }
        }

        touch[tp][col].clear();
        set<int>().swap(touch[tp][col]);
        touch[tp].erase(col);

        REP(j, TID) {
            int who = whose[j];
            if (tp!=j && (adj[j][tp]||adj[tp][j]) && par[who] == who && color[who] == col) {
                if (!tmpseen[who]) tomerge.pb(who), tmpseen[who] = 1;
            }
        }

    }else{
        // smol boi

        for (int hi : getadj(id)) {
            if (hi != id && color[hi] == col) {
                tomerge.pb(hi);
            }
        }
    }


    for (int t : tomerge) {
        mrg(id, t);
        tmpseen[t] = 0;
    }

    id = find(id);
    if (SZ(here[id]) < BS) {
        for (int hi : getadj(id)) {
            if (hi != id && color[hi] != col && touchpos[hi] != -1) {
                touch[touchpos[hi]][col].insert(id);
            }
        }
    }
}

signed main(){
    IOS();

    memset(touchpos, -1, sizeof touchpos);

    cin>>n>>m;
    vector<vector<int> > g;
    g.resize(n, vector<int> (m,0));
    REP(i,n) REP(j,m) {
        cin>>g[i][j]; g[i][j];
        here[getid(i,j)].pb(getid(i,j));
        color[getid(i,j)] = g[i][j];
        par[getid(i,j)] = getid(i,j);
    }

    REP(i,n) REP(j,m) {
        REP(t,4) {
            int I = i + dx[t], J = j + dy[t];
            if (ingrid(I,J) && color[getid(i,j)] == color[getid(I,J)]) {
                mrg(getid(i,j), getid(I,J));
            }
        }
    }

    int qu; cin>>qu;
    REP(ar, qu) {
        int r,c; cin>>r>>c;
        --r; --c;
        int ncol; cin>>ncol;

        go(getid(r,c), ncol);
    }

    REP(i,n) REP(j,m) {
        int it = getid(i,j);
        bug(it, find(it));
        if (find(it) == it) {
            for (int e : here[it]) {
                bug(e/m, e%m, color[it]);
                g[e/m][e%m] = color[it];
            }
        }
    }

    REP(i,n) REP(j,m) {
        cout<<g[i][j]<<" \n"[j==m-1];
    }


}

Compilation message (stderr)

paint.cpp: In function 'void go(int, int)':
paint.cpp:172:9: warning: unused variable 'r' [-Wunused-variable]
  172 |     int r = id/m, c = id%m;
      |         ^
paint.cpp:172:19: warning: unused variable 'c' [-Wunused-variable]
  172 |     int r = id/m, c = id%m;
      |                   ^

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