oj.uz

Submission #393481

# Submission time Handle Problem Language Result Execution time Memory
393481 2021-04-23T15:04:07 Z A_D Paint (COI20_paint) C++14
8 / 100
 3000 ms 25872 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];
int sz[N];
vector<int> st[N];
int a[N];
int x[]={0,0,1,-1};
int y[]={1,-1,0,0};
vector<ii> 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]){
        st[v].push_back(x);
        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({a[v],v});
                }
                else{
                    st[u].push_back(v);
                    sz[u]++;
                }
            }
            sort(vec.begin(),vec.end());
            for(auto x:vec){
//                cout<<x<<endl;
                compine(u,x.S);
            }
        }
    }
    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({sz[xx],xx});
        }
      //  cout<<endl;
        sort(vec.begin(),vec.end());
        for(auto x:vec){
            compine(u,x.S);
        }
    }
    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:77:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |             scanf("%d",&a[cnt]);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 9 ms 9676 KB Output is correct
3 Correct 14 ms 10204 KB Output is correct
4 Correct 18 ms 10220 KB Output is correct
5 Correct 789 ms 10520 KB Output is correct
6 Correct 2903 ms 10604 KB Output is correct
7 Correct 7 ms 9676 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 12224 KB Output is correct
2 Correct 770 ms 16148 KB Output is correct
3 Execution timed out 3082 ms 16452 KB Time limit exceeded

Subtask #3
0 / 31.0

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

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 20008 KB Output is correct
2 Execution timed out 3080 ms 18388 KB Time limit exceeded
3 Halted 0 ms 0 KB -