oj.uz

Submission #1067292

# Submission time Handle Problem Language Result Execution time Memory
1067292 2024-08-20T14:08:40 Z soncao Paint (COI20_paint) C++17
48 / 100
 3000 ms 58708 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 7 ms 18768 KB Output is correct
4 Correct 9 ms 18348 KB Output is correct
5 Correct 47 ms 18040 KB Output is correct
6 Correct 9 ms 17828 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 22360 KB Output is correct
2 Correct 50 ms 24500 KB Output is correct
3 Correct 68 ms 34648 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 58452 KB Output is correct
2 Correct 168 ms 58708 KB Output is correct
3 Correct 169 ms 58192 KB Output is correct
4 Correct 163 ms 56656 KB Output is correct
5 Correct 119 ms 54100 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 44372 KB Output is correct
2 Execution timed out 3077 ms 41080 KB Time limit exceeded
3 Halted 0 ms 0 KB -