Submission #393481

#	Time	Username	Problem	Language	Result	Execution time	Memory
393481		A_D	Paint (COI20_paint)	C++14	8 / 100	3086 ms	25872 KiB

paint

#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 (stderr)

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 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52