oj.uz

Submission #391968

# Submission time Handle Problem Language Result Execution time Memory
391968 2021-04-20T09:06:29 Z A_D Paint (COI20_paint) C++14
8 / 100
 3000 ms 66324 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 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(st[u].size()>st[v].size()){
        swap(u,v);
    }
    for(auto x:st[u]){
        st[v].insert(x);
    }
    st[v].erase(u);
    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];
            cout<<x<<" ";
        }
        cout<<endl;
    }
/*    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;
            cin>>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);
                }
            }
            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:132:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main()
      |      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 11 ms 14668 KB Output is correct
3 Correct 20 ms 16460 KB Output is correct
4 Correct 24 ms 16392 KB Output is correct
5 Correct 414 ms 16296 KB Output is correct
6 Correct 694 ms 16592 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 140 ms 20816 KB Output is correct
2 Correct 504 ms 33496 KB Output is correct
3 Execution timed out 3067 ms 31616 KB Time limit exceeded

Subtask #3
0 / 31.0

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

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 49940 KB Output is correct
2 Execution timed out 3058 ms 47540 KB Time limit exceeded
3 Halted 0 ms 0 KB -