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>
using namespace std;
#define N 20010
#define M 50
#define INFLL 2000000000000000020
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> pll;
ll h;
ll n,m;
ll head[N];
ll color[N];
bool marc[N];
unordered_set<ll>reach[N];
vector<ll>merges;
ll transform(ll i,ll j)
{
return i*m+j-m;
}
ll Dx[10]={-1,0,1,0};
ll Dy[10]={0,1,0,-1};
bool valid(ll i,ll j)
{
return (bool)(i>0 && i<=n && j>0 && j<=m);
}
void DFS(ll i,ll j)
{
ll x=transform(i,j),k,ni,nj,y;
marc[x]=true;
head[x]=h;
for(k=0;k<4;k++)
{
ni=i+Dx[k];
nj=j+Dy[k];
y=transform(ni,nj);
if(!valid(ni,nj))
continue;
if(color[y]==color[x])
{
if(!marc[y])
DFS(ni,nj);
}else
reach[h].insert(y);
}
return;
}
ll Find(ll u)
{
if(head[u]==u)
return u;
return head[u]=Find(head[u]);
}
void merge(ll u,ll v)
{
head[v]=u;
for(auto x : reach[v])
{
if(Find(x)==u)
continue;
reach[u].insert(x);
}
reach[u].erase(v);
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll q,x,i,j,c,u,v;
cin >> n >> m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
x=transform(i,j);
cin >> color[x];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
x=transform(i,j);
if(marc[x])
continue;
h=x;
DFS(i,j);
}
}
cin >> q;
while(q)
{
q--;
cin >> i >> j >> c;
x=transform(i,j);
u=Find(x);
color[u]=c;
for(auto r : reach[u])
{
v=Find(r);
if(u==v)
continue;
if(color[v]==c)
{
merges.pb(v);
}
}
while(!merges.empty())
{
merge(u,merges.back());
merges.pop_back();
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
x=transform(i,j);
u=Find(x);
cout << color[u] << ((j==m) ? '\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... |