oj.uz

Submission #540266

# Submission time Handle Problem Language Result Execution time Memory
540266 2022-03-19T18:34:21 Z RGBB Paint (COI20_paint) C++14
17 / 100
 3000 ms 196540 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];
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){
        int ni=findParent(i);
        if(nei[ni].find(b)!=nei[ni].end()||nei[b].find(ni)!=nei[b].end()){
            nei[ni].insert(a);
            nei[a].insert(ni);
        }
    }
}

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);
}

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){
        if(flag[i])continue;
        if(col[i]!=v)continue;
        if(nei[p].find(i)!=nei[p].end()||nei[i].find(p)!=nei[i].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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27348 KB Output is correct
2 Correct 18 ms 27536 KB Output is correct
3 Correct 44 ms 35008 KB Output is correct
4 Correct 61 ms 33120 KB Output is correct
5 Correct 42 ms 31836 KB Output is correct
6 Correct 181 ms 31148 KB Output is correct
7 Correct 16 ms 26964 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 55512 KB Output is correct
2 Correct 973 ms 69744 KB Output is correct
3 Correct 378 ms 83420 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 121904 KB Output is correct
2 Correct 1045 ms 126400 KB Output is correct
3 Execution timed out 3012 ms 196540 KB Time limit exceeded
4 Halted 0 ms 0 KB -