#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define M 50
#define INFLL 2000000000000000020
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> pint;
int h;
int n,m;
int head[N];
int color[N];
bool marc[N];
unordered_set<int>reach[N];
set<int>merges;
int transform(int i,int j)
{
return i*m+j-m;
}
int Dx[10]={-1,0,1,0};
int Dy[10]={0,1,0,-1};
bool valid(int i,int j)
{
return (bool)(i>0 && i<=n && j>0 && j<=m);
}
void DFS(int i,int j)
{
int 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;
}
int Find(int u)
{
if(head[u]==u)
return u;
return head[u]=Find(head[u]);
}
void merge(int u,int 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);
int 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.insert(v);
}
}
for(auto mm : merges)
{
merge(u,mm);
}
merges.clear();
}
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
12888 KB |
Output is correct |
2 |
Correct |
3 ms |
13148 KB |
Output is correct |
3 |
Correct |
8 ms |
15196 KB |
Output is correct |
4 |
Correct |
8 ms |
14892 KB |
Output is correct |
5 |
Correct |
153 ms |
94292 KB |
Output is correct |
6 |
Correct |
21 ms |
15192 KB |
Output is correct |
7 |
Correct |
2 ms |
12892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
20816 KB |
Output is correct |
2 |
Correct |
74 ms |
25380 KB |
Output is correct |
3 |
Correct |
393 ms |
41552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
157 ms |
61660 KB |
Output is correct |
2 |
Correct |
141 ms |
62164 KB |
Output is correct |
3 |
Correct |
162 ms |
61832 KB |
Output is correct |
4 |
Correct |
247 ms |
61852 KB |
Output is correct |
5 |
Correct |
445 ms |
57728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
110 ms |
46676 KB |
Output is correct |
2 |
Runtime error |
871 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |