Submission #540498

#	Time	Username	Problem	Language	Result	Execution time	Memory
540498		RGBB	Paint (COI20_paint)	C++14	48 / 100	3062 ms	239064 KiB

paint

#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int>pi;
typedef pair<ll,ll>pll;
typedef pair<double,double>pd;
typedef tuple<int,int,int>ti;
typedef tuple<ll,ll,ll>tll;
typedef tuple<double,double,double>td;
typedef complex<double>cd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbst;

mt19937 g1;
int get_random_int(int a,int b){
    return uniform_int_distribution<int>(a,b)(g1);
}

ll gcd(ll a,ll b){
    if(a==0)return b;
    return gcd(b%a,a);
}

const int MAX=2*1e5;
const int BLK=250;

int n,m,q;

vector<int>arr[MAX];

int par[MAX],si[MAX],col[MAX];
unordered_map<int,vector<int>>adj[MAX];//Colour, adjacent groups with that colour
unordered_set<int>nei[MAX];//All neighbors: not just by colour

bool flag[MAX];

bool isBig[MAX];
vector<int>blist;//List of blocks with size > BLK

int di[2]={0,-1},dj[2]={-1,0};

int findParent(int p){
    if(par[p]==p)return p;
    return par[p]=findParent(par[p]);
}

void connect(int a,int b){
    a=findParent(a);
    b=findParent(b);
    if(a==b)return;
    if(si[a]<si[b])swap(a,b);
    par[b]=a;
    si[a]+=si[b];
    flag[b]=true;
    for(auto&[i,j]:adj[b])for(auto&k:j)adj[a][i].push_back(k);
    adj[b].clear();
    for(auto&i:nei[b]){
        nei[a].insert(i);
        nei[i].insert(a);
    }
    nei[b].clear();
    if(si[a]>=BLK&&!isBig[a]){
        isBig[a]=true;
        blist.push_back(a);
    }
    for(int i:blist){
        if(flag[i])continue;
        if(nei[i].find(b)!=nei[i].end()){
            nei[i].insert(a);
            nei[a].insert(i);
        }
    }
}

void sq(int x,int y,int v){
    int p=findParent(x*m+y);
    vector<int>comb;
    for(auto&i:nei[p]){
        if(flag[i])continue;
        adj[i][v].push_back(p);
        if(col[i]==v)comb.push_back(i);
    }
    col[p]=v;
    for(int i:comb)connect(p,i);
}

bool check[MAX];

void bq(int x,int y,int v){
    int p=findParent(x*m+y);
    col[p]=v;
    vector<int>temp,comb,buff;
    if(adj[p].find(v)!=adj[p].end()){
        for(int i:adj[p][v]){
            int ni=findParent(i);
            if(!check[ni]){
                check[ni]=true;
                temp.push_back(ni);
                if(col[ni]==v)comb.push_back(ni);
            }
        }
    }
    for(int i:temp)check[i]=false;
    adj[p][v]=temp;
    for(int i:comb)connect(p,i);
    for(int i:blist){
        if(flag[i])continue;
        if(col[i]!=v)continue;
        if(nei[p].find(i)!=nei[p].end())buff.push_back(i);//this shit
    }
    for(int i:buff)connect(p,i);
}

void query(int x,int y,int v){
    int p=findParent(x*m+y);
    if(si[p]<BLK)sq(x,y,v);
    else bq(x,y,v);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n;i++)arr[i]=vector<int>(m);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>arr[i][j];
    for(int i=0;i<n*m;i++){
        par[i]=i;
        si[i]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<2;k++){
                int ni=i+di[k];
                int nj=j+dj[k];
                if(ni<0||ni>=n||nj<0||nj>=m)continue;
                if(arr[i][j]!=arr[ni][nj]){
                    int a=findParent(i*m+j);
                    int b=findParent(ni*m+nj);
                    adj[a][arr[ni][nj]].push_back(b);
                    nei[a].insert(b);
                    adj[b][arr[i][j]].push_back(a);
                    nei[b].insert(a);
                }
                else connect(i*m+j,ni*m+nj);
            }
        }
    }
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)col[findParent(i*m+j)]=arr[i][j];
    cin>>q;
    for(int i=0;i<q;i++){
        int x,y,v;
        cin>>x>>y>>v;
        x--;
        y--;
        query(x,y,v);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++)cout<<col[findParent(i*m+j)]<<" ";
        cout<<col[findParent(i*m+m-1)]<<"\n";
    }
}

Compilation message (stderr)

paint.cpp: In function 'void connect(int, int)':
paint.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto&[i,j]:adj[b])for(auto&k:j)adj[a][i].push_back(k);
      |              ^

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