oj.uz

Submission #393469

# Submission time Handle Problem Language Result Execution time Memory
393469 2021-04-23T14:20:18 Z A_D Paint (COI20_paint) C++14
8 / 100
 3000 ms 64208 KB 
#include <bits/stdc++.h>
//#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
int n,m;
const int N=2e5+10;
vector<int> idx[N];
int p[N];
set<int> st[N];
int sz[N];
int a[N];
int x[]={0,0,1,-1};
int y[]={1,-1,0,0};
vector<int> vec;
bool out(int i,int j)
{
    //cout<<i<<" "<<j<<endl;
    bool ans=i<1||j<1||i>n||j>m;
    return ans;
}
int find(int u)
{
    if(u==p[u])return u;
    return p[u]=find(p[u]);
}
void compine(int u,int v)
{
    u=find(u);
    v=find(v);
    if(u==v)return;
    if(sz[u]>sz[v]){
        swap(u,v);
    }
    for(auto x:st[u]){
        if(st[v].find(x)==st[v].end())sz[v]++;
        st[v].insert(x);
    }
    st[v].erase(u);
    sz[v]--;
    p[u]=v;
}
void fix()
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=idx[i][j];
            x=find(x);
            x=a[x];
            printf("%d ",x);
        }
        printf("\n");
    }
/*    cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=idx[i][j];
            x=find(x);
            cout<<x<<" ";
        }
        cout<<endl;
    }
*/
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        idx[i].resize(m+10);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cnt++;
            p[cnt]=cnt;
            idx[i][j]=cnt;
            scanf("%d",&a[cnt]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            vec.clear();
            int u=idx[i][j];
            int c=a[u];
            u=find(u);
            for(int k=0;k<4;k++){
                int ni=i+x[k];
                int nj=j+y[k];

                if(out(ni,nj))continue;

                int v=idx[ni][nj];

                int nc=a[v];

                if(c==nc){
                    vec.push_back(v);
                }
                else{
                    st[u].insert(v);
                    sz[u]++;
                }
            }
            for(auto x:vec){
//                cout<<x<<endl;
                compine(u,x);
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
//        cout<<"\n\n";
  //      fix();
    //    cout<<"\n\n";
        int c,i,j;
        cin>>i>>j>>c;
        int u=idx[i][j];
        u=find(u);
        a[u]=c;
        vec.clear();
        for(auto x:st[u]){
            int xx=find(x);
//            cout<<x<<" ";
            if(a[xx]==c)vec.push_back(xx);
        }
      //  cout<<endl;
        for(auto x:vec){
            compine(u,x);
        }
    }
    fix();
}
main()
{
    //freopen(".in","r",stdin);freopen(".out","w",stdout);
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message

paint.cpp:136:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main()
      |      ^
paint.cpp: In function 'void solve()':
paint.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |             scanf("%d",&a[cnt]);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 10 ms 14552 KB Output is correct
3 Correct 18 ms 16344 KB Output is correct
4 Correct 23 ms 16248 KB Output is correct
5 Correct 419 ms 16124 KB Output is correct
6 Correct 740 ms 16452 KB Output is correct
7 Correct 9 ms 14284 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 20388 KB Output is correct
2 Correct 492 ms 32288 KB Output is correct
3 Execution timed out 3095 ms 34008 KB Time limit exceeded

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 64208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 48744 KB Output is correct
2 Execution timed out 3099 ms 44520 KB Time limit exceeded
3 Halted 0 ms 0 KB -