Submission #390846

#	Time	Username	Problem	Language	Result	Execution time	Memory
390846		A_D	Paint (COI20_paint)	C++14	0 / 100	203 ms	61408 KiB

paint

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+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 find(int u)
{
    if(u==p[u])return u;
    return p[u]=find(p[u]);
}
void compine(int u,int v,int c)
{
    u=find(u);
    v=find(v);
    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 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++;
            scanf("%d",&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("%d",&i);
        scanf("%d",&j);
        scanf("%d",&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){
            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 (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52