제출 #554417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554417		leaked	Paint (COI20_paint)	C++17	0 / 100	609 ms	524288 KiB

paint

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) ((ull)(1)<<(x))
#define sz(x) (int)(x).size()
#define vec vector

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
const int K=100;
const int tx[4]={1,-1,0,0};
const int ty[4]={0,0,1,-1};

int who[K],p[N],cnt[N],id[N];
ull ust[N];
unordered_map<int,int> ids[N];
/// for comp lets mantain colours
vec<int> go[N][K];
int clr[N];
int j=0;
int get(int v){
    return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b,bool need=0){
//    cout<<"MEG "<<a<<' '<<b<<endl;
    a=get(a),b=get(b);
//        cout<<"MEG "<<a<<' '<<b<<endl;

    if(a==b) return 0;

    if(cnt[a]>cnt[b]) swap(a,b);
    for(int i=0;i<j;i++){
        for(auto &z : go[a][i])
            go[b][i].pb(z);
        go[a][i].clear();
    }
    if(id[a]!=-1) id[b]=id[a];
//        ust[b]|=ust[a];/// n*k/64;
    p[a]=b;cnt[b]+=cnt[a];

//        cout<<"IMG "<<a<<' '<<b<<endl;

    if(need){
        ust[b]|=ust[a];/// n*k/64;

        if(id[b]!=-1){
            for(int j=0;j<K;j++){
                if(ust[b]&pw(j) && who[j]!=-1){
                    ust[get(who[j])]|=pw(id[b]);
                }
            }
        }
    }
//    cout<<"EXIT "<<endl;
    return 1;
}
int n,m;
int idl(int i,int j){
    return i*m+j;
}



signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    cout<<pw(63)<<endl;
//    return 0;
    iota(p,p+N,0);fill(cnt,cnt+N,1);
    cin>>n>>m;
    vec<vec<int>>a(n,vec<int>(m));
    vec<int>b(n*m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            b[i*m+j]=a[i][j];
        }
    }
    int q;
    cin>>q;
    vec<int> ii(q),jj(q),c(q);
    for(int i=0;i<q;i++){
        cin>>ii[i]>>jj[i]>>c[i];--ii[i];--jj[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i && a[i-1][j]==a[i][j]) mg(idl(i,j),idl(i-1,j));
            if(j && a[i][j-1]==a[i][j]) mg(idl(i,j),idl(i,j-1));
        }
    }
//    for(int i=0;i<n;i++){
//        for(int j=0;j<m;j++)
//            cout<<ds.get(id(i,j))<<' ';
//        cout<<'\n';
//    }
//    return 0;
    vec<int>used(n*m,-1);
    int tt=1;
    fill(who,who+K,-1);
    for(int t=0;t<q;t+=K){
        int l=t,r=min(q,t+K);
        for(int i=0;i<n*m;i++) id[i]=-1,clr[b[i]]=-1,ust[i]=0;
        ++tt;
        for(int i=l;i<r;i++){
            int v=get(idl(ii[i],jj[i]));
            who[i-l]=-1;
            if(clr[c[i]]==-1){
                clr[c[i]]=j++;
            }
            if(used[v]!=t){
                id[v]=i-l;
                used[v]=t;
                who[i-l]=v;
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int v=get(idl(i,j));
                for(int x=0;x<4;x++){
                    int ni=tx[x]+i,nj=ty[x]+j;
                    if(ni>=0&&ni<n&&nj>=0&&nj<m){
                        int u=get(idl(ni,nj));
                        if(used[v]==t)
                            ust[u]|=pw(id[v]);
                        if(clr[b[u]]!=-1)
                            go[v][clr[b[u]]].pb(u);
                    }
                }
            }
        }

        for(int i=l;i<r;i++){
            int v=get(idl(ii[i],jj[i]));
            b[v]=c[i];
            if(ids[v].find(b[v])!=ids[v].end()){
                int j=ids[v][b[v]];
                vec<int> me=go[v][j];
                for(auto &z : me){
                    if(b[get(z)]==b[v])
                        mg(v,z,1);
                }
                go[v][j].clear();
            }
            for(int j=0;j<K;j++){
                if(who[j]!=-1 && b[get(who[j])]==b[v] && ust[v]&pw(j))
                    mg(who[j],v,1);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int v=get(idl(i,j));
                for(int x=0;x<4;x++){
                    int ni=tx[x]+i,nj=ty[x]+j;
                    if(ni>=0&&ni<n&&nj>=0&&nj<m){
                        int u=get(idl(ni,nj));
                        if(clr[b[u]]!=-1)
                            go[v][clr[b[u]]].clear();
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cout<<b[get(idl(i,j))]<<' ';
        cout<<'\n';
    }
    return 0;
}
/*
6 6
1 2 1 2 2 2
2 1 2 1 3 1
2 3 3 2 3 2
2 2 1 2 2 2
2 2 2 2 2 2
2 2 2 2 2 1

6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 2 2 2 2 1

6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 2 2 2 2 1


6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 2 2 2 2 1
*/

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