oj.uz

답안 #540498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540498 2022-03-20T15:02:35 Z RGBB Paint (COI20_paint) C++14
48 / 100
 3000 ms 239064 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){
        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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 27348 KB Output is correct
2 Correct 19 ms 27596 KB Output is correct
3 Correct 37 ms 35100 KB Output is correct
4 Correct 50 ms 33072 KB Output is correct
5 Correct 37 ms 31736 KB Output is correct
6 Correct 36 ms 31140 KB Output is correct
7 Correct 16 ms 26868 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 55392 KB Output is correct
2 Correct 661 ms 67836 KB Output is correct
3 Correct 336 ms 82996 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 120676 KB Output is correct
2 Correct 655 ms 119652 KB Output is correct
3 Correct 785 ms 121392 KB Output is correct
4 Correct 1162 ms 122184 KB Output is correct
5 Correct 819 ms 114360 KB Output is correct

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 828 ms 120752 KB Output is correct
2 Correct 1027 ms 126548 KB Output is correct
3 Correct 2728 ms 196220 KB Output is correct
4 Correct 1730 ms 113404 KB Output is correct
5 Execution timed out 3062 ms 239064 KB Time limit exceeded
6 Halted 0 ms 0 KB -