oj.uz

Submission #540499

# Submission time Handle Problem Language Result Execution time Memory
540499 2022-03-20T15:08:01 Z RGBB Paint (COI20_paint) C++14
8 / 100
 3000 ms 429084 KB 
#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];
gp_hash_table<int,vector<int>>adj[MAX];//Colour, adjacent groups with that colour
gp_hash_table<int,bool>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};

void init(){
    for(int i=0;i<n*m;i++){
        par[i]=i;
        si[i]=1;
    }
}

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,j]:nei[b]){
        nei[a][i]=true;
        nei[i][a]=true;
    }
    nei[b].clear();
    if(si[a]>=BLK&&!isBig[a]){
        isBig[a]=true;
        blist.push_back(a);
    }
    for(int i:blist){
        int ni=findParent(i);
        if(nei[ni].find(b)!=nei[ni].end()||nei[b].find(ni)!=nei[b].end()){
            nei[ni][a]=true;
            nei[a][ni]=true;
        }
    }
}

void sq(int x,int y,int v){
    int p=findParent(x*m+y);
    vector<int>comb;
    for(auto&[i,j]: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);
}

void bq(int x,int y,int v){
    int p=findParent(x*m+y);
    col[p]=v;
    vector<int>comb,buff;
    if(adj[p].find(v)!=adj[p].end()){
        for(int i:adj[p][v]){
            int ni=findParent(i);
            if(col[ni]==v)comb.push_back(ni);
        }
    }
    for(int i:comb)connect(p,i);
    for(int i:blist){
        int ni=findParent(i);
        if(col[ni]!=v)continue;
        if(nei[p].find(ni)!=nei[p].end()||nei[ni].find(p)!=nei[ni].end())buff.push_back(ni);//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];
    init();
    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][b]=true;
                    adj[b][arr[i][j]].push_back(a);
                    nei[b][a]=true;
                }
                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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 133640 KB Output is correct
2 Correct 103 ms 133556 KB Output is correct
3 Correct 129 ms 140072 KB Output is correct
4 Correct 135 ms 139460 KB Output is correct
5 Correct 114 ms 136852 KB Output is correct
6 Correct 246 ms 136124 KB Output is correct
7 Correct 94 ms 133400 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 155396 KB Output is correct
2 Correct 695 ms 150852 KB Output is correct
3 Execution timed out 3031 ms 149944 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3103 ms 177816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 209552 KB Output is correct
2 Correct 855 ms 205096 KB Output is correct
3 Correct 2416 ms 348060 KB Output is correct
4 Correct 1419 ms 222064 KB Output is correct
5 Execution timed out 3095 ms 429084 KB Time limit exceeded
6 Halted 0 ms 0 KB -