Submission #562559

#	Time	Username	Problem	Language	Result	Execution time	Memory
562559		Redhood	Paint (COI20_paint)	C++14	0 / 100	3084 ms	129332 KiB

paint

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair


using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;






typedef long long ll;
typedef long double ld;



vector < vector < int > > g;

const int N = (int)2e5 + 10;
const int buben = 300;




gp_hash_table<int,vector<int>> st[N];
int p[N], cur_color[N], sz[N];
void make(int v, int C){
    p[v] = v;
    cur_color[v] = C;
}
void make(int v){
    p[v]=v;
    st[v].clear();
    sz[v] = 0;
}
int fin(int v){
    if(p[v] == v)return v;
    return p[v] = fin(p[v]);
}
void un(int a , int b){
    a = fin(a) , b = fin(b);
    if(a == b)
        return;
    if(sz[a] < sz[b])
        swap(a , b);
    p[b] = a;
    sz[a] += sz[b];
    for(auto &u : st[b]){
        for(auto &x : u.se)
            st[a][u.fi].pb(x);
    }
}


vector < pair < int , int > > dir = {{-1,0},{+1,0},{0,-1},{0,+1}};
int r , s;
bool valid(int x , int y){
    if(x >= 0 && x < r && y >= 0 && y < s)
        return true;
    return false;
}
bool onezero = 1;


vector < int > prv;
void makeit(int cell, int clr){
    cell = fin(cell);


    vector < int > unite_with;
    while(!st[cell][clr].empty()){
        int t = st[cell][clr].back();
        sz[cell]--;
        st[cell][clr].pop_back();
        if(cur_color[fin(t)] == clr)
            unite_with.pb(t);
    }
    for(auto &u : prv){
        if(cur_color[fin(u)] == clr)
            unite_with.pb(fin(u));
    }
    for(auto &j : unite_with){
        un(cell , j);
    }
    cur_color[fin(cell)] = clr;
    prv.pb(fin(cell));
}
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    cin >> r >> s;
    g.resize(r , vector < int > (s));

    for(int i = 0; i < r; ++i)
        for(int j = 0; j < s; ++j){
            cin >> g[i][j];
        }


    /// the idea is the following right


    /// we have

    int q;
    cin >> q;
    vector < array < int , 3 > > que(q);
    for(int i = 0; i < q; ++i){
        cin >> que[i][0] >> que[i][1] >> que[i][2];
        que[i][0]--, que[i][1]--;
    }

    for(int it = 0; it <= q/buben; ++it){
        int li = it * buben , ri = min(q - 1, (it+1)*buben - 1);


        /// build it
        for(int t = 0; t < r * s; ++t){
            make(t);

        }
        prv.clear();
        for(int i = 0; i < r; ++i)
        for(int j = 0; j < s; ++j){
            for(auto &u : dir){
                int i1 = u.fi + i, j1 = j + u.se;
                if(valid(i1 , j1)){
                    if(g[i1][j1] == g[i][j])
                        un(i1 * s + j1 , i * s + j);

                }
            }
        }
        for(int i = 0; i < r; ++i)
        for(int j = 0; j < s; ++j){
            cur_color[fin(i * s + j)] = g[i][j];
            for(auto &u : dir){
                int i1 = u.fi + i, j1 = j + u.se;
                if(valid(i1 , j1)){
                    if(g[i1][j1] != g[i][j]){
                        int a = fin(i1 * s + j1);
                        int b = fin(i * s + j);
                        sz[a]++, sz[b]++;
                        st[a][g[i][j]].pb(b);
                        st[b][g[i1][j1]].pb(a);
                    }
                }
            }
        }





        /// okay
        for(int t = li; t <= ri; ++t){
            int id = que[t][0] * s + que[t][1];
            makeit(id, que[t][2]);
        }



        for(int i = 0; i < r; ++i){
            for(int j = 0; j < s; ++j){
                g[i][j] = cur_color[fin(i * s + j)];
            }
        }

        /// update g
    }

    for(int i = 0; i < r; ++i){
        for(int j = 0; j < s; ++j){
            cout << g[i][j] << ' ';
        }
        cout << '\n';
    }




    return 0;
}

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