Submission #907745

#	Time	Username	Problem	Language	Result	Execution time	Memory
907745		ibm2006	Paint (COI20_paint)	C++17	0 / 100	3089 ms	66892 KiB

paint

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,m,ee,e;
vector<vector<ll>> a,h;
vector<vector<pair<ll,ll>>> par;
vector<vector<set<pair<ll,pair<ll,ll>>>>> v;
pair<ll,ll> p,q;
pair<ll,pair<ll,ll>> pq;
void adj(ll x,ll y)
{
    ll i,j;
    if(a[x+1][y]>=0)
    {
        v[x][y].insert({a[x+1][y],{x+1,y}});
    }
    if(a[x-1][y]>=0)
    {
        v[x][y].insert({a[x-1][y],{x-1,y}});
    }
    if(a[x][y+1]>=0)
    {
        v[x][y].insert({a[x][y+1],{x,y+1}});
    }
    if(a[x][y-1]>=0)
    {
        v[x][y].insert({a[x][y-1],{x,y-1}});
    }
}
pair<ll,ll> f(ll x,ll y)
{
    pair<ll,ll> p={x,y};
    if(par[x][y]==p)
        return p;
    par[x][y]=f(par[x][y].first,par[x][y].second);
    return par[x][y];
}
void g(ll x,ll y,ll z,ll w)
{
    ll i;
    pair<ll,ll> p,q;
    p=f(x,y);
    q=f(z,w);
    if(p==q)
        return;
        x=p.first;  y=p.second;
        z=q.first;  w=q.second;
    if(h[x][y]>h[z][w])
    {
        h[x][y]+=h[z][w];
        par[z][w]={x,y};
        for(pair<ll,pair<ll,ll>> pa:v[z][w])
            v[x][y].insert(pa);
        v[z][w].clear();
        return;
    }
    else
    {
        h[z][w]+=h[x][y];
        par[x][y]={z,w};
        for(pair<ll,pair<ll,ll>> pa:v[x][y])
            v[z][w].insert(pa);
        v[x][y].clear();
        return;
    }
}
int main()
{
    scanf("%lld %lld",&n,&m);
    a.resize(n+10);
    v.resize(n+10);
    par.resize(n+10);
    h.resize(n+10);
    for(i=0;i<=n+1;i++)
    {
        a[i].resize(m+10);
        v[i].resize(m+10);
        par[i].resize(m+10);
        h[i].resize(m+10);
    }
    for(i=0;i<=n+1;i++)
    {
        for(j=0;j<=m+1;j++)
        {
            a[i][j]=-1;
            par[i][j]={i,j};
            h[i][j]=1;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%lld",&a[i][j]);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            adj(i,j);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(par[i][j]!=make_pair(i,j))
                continue;
            //    printf("(%lld,%lld)\n",i,j);
            while(1)
            {
             //   printf("!");
                z=i;
                w=j;
                p=f(z,w);
                z=p.first;
                w=p.second;
                x=a[z][w];
            //    printf("?");
            if(v[z][w].lower_bound({x,{0,0}})==v[z][w].end())
                break;
            pq=(*v[z][w].lower_bound({x,{0,0}}));
            if(pq.first!=x)
                break;
            v[z][w].erase(pq);
           // printf("@");
            p=pq.second;
            x=p.first;
            y=p.second;
          //  printf("?");
           // printf("(%lld,%lld)",x,y);
            p=f(x,y);
           // printf("!");
            x=p.first;
            y=p.second;
           // printf("%lld,%lld,%lld,%lld\n",x,y,z,w);
            g(x,y,z,w);
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            p=f(i,j);
            x=p.first;  y=p.second;
           // printf("(%lld,%lld)",x,y);
           // printf("%lld ",a[x][y]);
        }
       // printf("\n");
    }
    scanf("%lld",&e);
    for(ee=0;ee<e;ee++)
    {
        scanf("%lld %lld %lld",&i,&j,&z);
        p=f(i,j);
        i=p.first;
        j=p.second;
        a[i][j]=z;
       while(1)
            {
               // printf("!");
                z=i;
                w=j;
                p=f(z,w);
                z=p.first;
                w=p.second;
                x=a[z][w];
              //  printf("?");
            if(v[z][w].lower_bound({x,{0,0}})==v[z][w].end())
                break;
            pq=(*v[z][w].lower_bound({x,{0,0}}));
            if(pq.first!=x)
                break;
            v[z][w].erase(pq);
            //printf("@");
            p=pq.second;
            p=f(p.first,p.second);
            x=p.first;
            y=p.second;
            if(a[x][y]!=a[z][w])
                continue;
           // printf("?");
           // printf("(%lld,%lld)",x,y);
            p=f(x,y);
           // printf("!");
            x=p.first;
            y=p.second;
           // printf("%lld,%lld,%lld,%lld\n",x,y,z,w);
            g(x,y,z,w);
            }
            for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            p=f(i,j);
            x=p.first;  y=p.second;
            //printf("[%lld] ",a[x][y]);
        }
      //  printf("\n");
    }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            p=f(i,j);
            x=p.first;  y=p.second;
            printf("%lld ",a[x][y]);
        }
        printf("\n");
    }
}

Compilation message (stderr)

paint.cpp: In function 'void adj(ll, ll)':
paint.cpp:12:8: warning: unused variable 'i' [-Wunused-variable]
   12 |     ll i,j;
      |        ^
paint.cpp:12:10: warning: unused variable 'j' [-Wunused-variable]
   12 |     ll i,j;
      |          ^
paint.cpp: In function 'void g(ll, ll, ll, ll)':
paint.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |     if(p==q)
      |     ^~
paint.cpp:46:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   46 |         x=p.first;  y=p.second;
      |         ^
paint.cpp:40:8: warning: unused variable 'i' [-Wunused-variable]
   40 |     ll i;
      |        ^
paint.cpp: In function 'int main()':
paint.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |             scanf("%lld",&a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:153:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |     scanf("%lld",&e);
      |     ~~~~~^~~~~~~~~~~
paint.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         scanf("%lld %lld %lld",&i,&j,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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