This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |