Submission #1067292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067292		soncao	Paint (COI20_paint)	C++17	48 / 100	3077 ms	58708 KiB

paint

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ii pair<int,int>
#define lll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ii>
int n,m,q,a[1000005];
int cv(int i,int j){
    if(i>n||i<1)return -1;
    if(j>m||j<1)return -1;
    return(m*(i-1)+j);
}
int lab[1000005],cl[1000005];
void setup(){
    for(int i=1;i<=n*m;i++){
        lab[i]=i;
    }
}
int findset(int u){
    return (u==lab[u])?u:(lab[u]=findset(lab[u]));
}
set<int>G[300005];
void unions(int u,int v){
    if(u==-1||v==-1)return;
    u=findset(u);v=findset(v);
    if(u==v)return;
    //if(u>v)swap(u,v);
    if(cl[u]!=cl[v]){
        G[u].insert(v);
        G[v].insert(u);
        return;
    }
    if(G[u].size()<G[v].size())swap(u,v);
    lab[v]=u;
    G[u].erase(v);
    G[v].erase(u);
    for(int it:G[v]){
        G[u].insert(it);
        G[it].erase(v);
        G[it].insert(u);
    }
    G[v].clear();
}
void sc()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>cl[cv(i,j)];
        }
    }
    setup();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
          //  unions(cv(i,j),cv(i,j-1));
            int t=cv(i,j);
            unions(t,cv(i,j+1));
         //  unions(cv(i,j),cv(i-1,j));
            unions(t,cv(i+1,j));
        }
    }
    cin>>q;
   // for(int it:G[1])cout<<it<<' '<<'\n';
    while(q--){
        int r,s,c;cin>>r>>s>>c;
        int t=cv(r,s);
       // cout<<t<<' ';
        t=findset(t);
       // cout<<t<<'\n';
        cl[t]=c;
        vi save;
        for(int it:G[t]){
            if(cl[t]==cl[it]){
                //G[t].erase(it);G[it].erase(t);
              //  cout<<t<<' '<<it<<'\n';
                save.push_back(it);
               // cout<<it<<' ';
            }
        }
        //t=findset(t);
        for(int it:save)unions(t,it);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<cl[findset(cv(i,j))]<<" \n"[j==m];
        }
    }
}
int main()
{
  // freopen("mai.inp","r",stdin);
//   freopen("mai.out","w",stdout);
    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    sc() ;
    return 0 ; ///sc
}

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