Submission #562858

#	Time	Username	Problem	Language	Result	Execution time	Memory
562858		Redhood	Paint (COI20_paint)	C++14	100 / 100	438 ms	76744 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 = 320;


vector < int > neighbours[N];
int sz[N], cur_color[N] ,p[N] , r , s;
bool large[N];
unordered_map < int , vector < int > > bycolor[N];
set < int > big[N];

bool valid(int x , int y){
    if(x >= 0 && x < r && y >= 0 && y < s)
        return true;
    return false;
}
void make(int v, int C){
    p[v] = v;
    sz[v] = 1;
    cur_color[v] = C;
}
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);
    sz[a] += sz[b];
    p[b] = a;


//    if(!large[a]){
        for(auto &f : big[b]){
            int u = fin(f);
            if(u != a)
                big[a].insert(u);
        }
//    }

    if(sz[a] > buben && !large[a]){
        large[a] = 1;
        for(auto &u : neighbours[a]){
            u = fin(u);
            if(u != a){
                bycolor[a][cur_color[u]].push_back(u);
                big[u].insert(a);
            }
        }
    }
    if(large[a]){
        for(auto &u : neighbours[b]){
            u = fin(u);
            if(u != a){
                bycolor[a][cur_color[u]].push_back(u);
                big[u].insert(a);
            }
        }
    }
    for(auto &u : neighbours[b])
        neighbours[a].pb(u);

}
/// so
void makeit(int x , int y , int c){
    int cell = fin(x * s + y);
    vector < int > unite_with;
    if(large[cell]){
        for(auto &u : bycolor[cell][c]){
            if(cur_color[fin(u)] == c)
                unite_with.pb(fin(u));
        }
        bycolor[cell][c].clear();
    }else{
        for(auto &u : neighbours[cell]){
            u = fin(u);
            if(u != cell && cur_color[u] == c){
                unite_with.push_back(u);
            }
        }
    }
    for(auto &x : unite_with)
        un(cell , x);
    cell = fin(cell);
    cur_color[cell] = c;
//    if(!large[cell]){
    vector<int>del,ins;
        for(auto &f : big[cell]){
            int u = fin(f);
            if(u != f){
                del.pb(f);
                ins.pb(u);
            }
        }
    for(auto &u :del){
//        if(big[cell].find(u) == big[cell].end())
//        exit(0);
        big[cell].erase(u);
    }
    for(auto &u : ins)big[cell].insert(u);
    for(auto &u : big[cell]){
        bycolor[u][c].pb(cell);
    }
//    }


}
vector < pair < int , int > > dir = {{-1 ,0}, {+1 , 0}, {0 , -1} , {0 , + 1}};
void find_neighb(int x , int y){
    for(auto &u : dir){
        int i = x + u.fi, j  = y + u.se;
        if(valid(i , j) && g[i][j] != g[x][y]){
            neighbours[x * s + y].pb(i * s + j);
        }
    }
}
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];
        }
    }
    for(int i = 0; i < r; ++i){
        for(int j =0 ; j < s; ++j){
            make(i * s + j, g[i][j]);
            find_neighb(i , j);
        }
    }
    for(int i = 0; i < r; ++i){
        for(int j = 0; j < s; ++j){
            for(auto &u : dir){
                int a = i + u.fi , b = j + u.se;
                if(valid(a , b) && g[a][b] == g[i][j]){
                    un(a * s + b , i * s + j);
                }
            }
        }
    }

    int q;
    cin >> q;
    for(int i = 0; i < q; ++i){
        int x , y , c;
        cin >> x >> y >> c;
        --x, --y;
        makeit(x , y , c);
    }
    for(int i = 0; i < r; ++i){
        for(int j = 0; j < s; ++j){
            cout << cur_color[fin(i * s + j)] << ' ';
        }
        cout << '\n';
    }





    return 0;
}

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