oj.uz

Submission #390842

# Submission time Handle Problem Language Result Execution time Memory
390842 2021-04-17T07:43:07 Z A_D Paint (COI20_paint) C++14
0 / 100
 360 ms 524292 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100;
int a[N];
vector<int> idx[N];
int p[N];
set<int> st[N];
vector<int> vec;
set<int> q;
int x[]={0,0,1,-1 };
int y[]={1,-1,0,0 };
/*
int fin(int u)
{
    if(u==p[u]){
        for(auto x:q){
            st[u].insert(x);
        }
        return u;
    }
    for(auto x:st[u])q.insert(st[u]);
    st[u].clear();
    return fin(p[u]);
}
*/
int find(int u)
{
    if(u==p[u])return u;
    /*
    q.clear();
    return fin(u);
    */
    return p[u]=find(p[u]);
}
void compine(int u,int v,int c)
{
    if(st[u].size()>st[v].size())swap(u,v);
    p[u]=v;
    for(auto x:st[u])st[v].insert(x);
    st[u].clear();
    a[v]=c;
}
int n,m;
void fix()
{
    cout<<"\n\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int me=idx[i][j];
            me=find(me);
            cout<<a[me]<<" ";
        }
        cout<<endl;
    }
    cout<<"\n\n";
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        idx[i].resize(m+1);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cnt++;
            scanf("%lld",&a[cnt]);
            p[cnt]=cnt;
            idx[i][j]=cnt;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int i1=idx[i][j];
            int u=find(i1);
            vec.clear();
            for(int k=0;k<4;k++){
                int ni=i+x[k];
                int nj=j+y[k];
                if(min(ni,nj)==0)continue;
                if(ni>n||nj>m)continue;
                int i2=idx[ni][nj];
                int v=find(i2);
                if(a[i1]==a[i2]){
                    if(u!=v){
                        vec.push_back(v);
                    }
                }
                else{
                    st[u].insert(v);
                }
            }
            for(auto x:vec){
                compine(u,x,a[u]);
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
  //      fix();
        int c,i,j;
        scanf("%lld",&i);
        scanf("%lld",&j);
        scanf("%lld",&c);
        int me=idx[i][j];
        me=find(me);
       // if(!q)cout<<me<<" "<<a[me]<<endl;
        if(a[me]==c)continue;
        a[me]=c;
        vec.clear();
        for(auto x:st[me]){
            if(a[x]==c)vec.push_back(x);
        }
        for(auto x:vec){
            me=find(me);
            st[me].erase(x);
            compine(me,x,c);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int me=idx[i][j];
            me=find(me);
            cout<<a[me]<<" ";
        }
        cout<<endl;
    }
}
main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message

paint.cpp:131:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  131 | main()
      |      ^
paint.cpp: In function 'void solve()':
paint.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |             scanf("%lld",&a[cnt]);
      |             ~~~~~^~~~~~~~~~~~~~~~
paint.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |         scanf("%lld",&i);
      |         ~~~~~^~~~~~~~~~~
paint.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         scanf("%lld",&j);
      |         ~~~~~^~~~~~~~~~~
paint.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |         scanf("%lld",&c);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14540 KB Output is correct
2 Runtime error 360 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 322 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 318 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -