oj.uz

Submission #446615

# Submission time Handle Problem Language Result Execution time Memory
446615 2021-07-22T19:26:01 Z MOUF_MAHMALAT Paint (COI20_paint) C++11
31 / 100
 258 ms 84816 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,m,a[200009],p[200009],sz[200009],q;
map<ll,vector<ll> >mp[200009];
ll op(ll x,ll y)
{
    if(x<0||x>=n||y<0||y>=m)
        return -1;
    return x*m+y;
}
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y||a[x]!=a[y])
        return;
    if(sz[x]<sz[y])
        swap(x,y);
    p[y]=x;
    sz[x]+=sz[y];
    for(auto z:mp[y])
    {
        for(auto u:z.second)
            mp[x][z.first].push_back(u);
    }
}
void go(ll o)
{
    o=gp(o);
    vector<ll>v=mp[o][a[o]];
    mp[o][a[o]].clear();
    sz[o]-=v.size();
    for(auto z:v)
        mrg(z,o);
    if(o==gp(o))
        return;
    go(gp(o));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(ll i=0; i<n*m; i++)
    {
        cin>>a[i];
        p[i]=i;
    }
    for(ll i=0; i<n; i++)
        for(ll j=0; j<m; j++)
        {
            ll o=op(i,j),k;
            k=op(i-1,j);
            if(k>-1)
                mp[o][a[k]].push_back(k),sz[o]++;
            k=op(i,j+1);
            if(k>-1)
                mp[o][a[k]].push_back(k),sz[o]++;
            k=op(i,j-1);
            if(k>-1)
                mp[o][a[k]].push_back(k),sz[o]++;
            k=op(i+1,j);
            if(k>-1)
                mp[o][a[k]].push_back(k),sz[o]++;
        }
    for(ll i=0; i<n*m; i++)
        go(i);
    cin>>q;
    while(q--)
    {
        ll x,y,val,o;
        cin>>x>>y>>val;
        o=op(x-1,y-1);
        o=gp(o);
        a[o]=val;
        go(o);
    }
    for(ll i=0; i<n; i++)
    {
        for(ll j=0; j<m; j++)
        {
            ll o=op(i,j);
            o=gp(o);
            cout<<a[o]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10060 KB Output is correct
2 Correct 7 ms 10188 KB Output is correct
3 Incorrect 19 ms 15172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 30120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 54740 KB Output is correct
2 Correct 234 ms 53880 KB Output is correct
3 Correct 190 ms 54896 KB Output is correct
4 Correct 222 ms 54268 KB Output is correct
5 Correct 193 ms 51524 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 84816 KB Output isn't correct
2 Halted 0 ms 0 KB -