#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ft first
#define sd second
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
using namespace __gnu_pbds;
const int N = 200100;
const int BLOCK = 400;
vector<i2> elms;
bool init_mrk[N];
int n, m, pre[N];
int c[N], who[N];
int used[N], tt = 0;
int stp[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
struct comp{
int color;
vector<i2> pnts;
vector<int> big_neib;
bool large;
gp_hash_table<int, vector<int> > by_color;
};
vector<comp> comps;
int get_pre(int x) { return (pre[x] == x ? x : pre[x] = get_pre(pre[x])); }
void init_dfs(int x, int y, int now){
if (x < 0 || y < 0 || x >= n || y >= m) return;
if (init_mrk[x * m + y]) return;
if (c[x * m + y] != now) return;
elms.PB({x, y});
init_mrk[x * m + y] = 1;
who[x * m + y] = sz(comps);
for (int it = 0; it < 4; it++){
int cx = x + stp[it][0];
int cy = y + stp[it][1];
init_dfs(cx, cy, now);
}
}
void declare_big(comp &now){
now.large = 1;
tt++;
for (i2 CR : now.pnts){
int x = CR[0], y = CR[1];
int cur_comp = who[x * m + y];
for (int it = 0; it < 4; it++){
int cx = x + stp[it][0];
int cy = y + stp[it][1];
if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
int co_id = who[cx * m + cy];
if (used[co_id] < tt){
used[co_id] = tt;
comps[co_id].big_neib.PB(cur_comp);
comps[cur_comp].by_color[comps[co_id].color].PB(co_id);
}
}
}
}
void Init(){
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> c[i * m + j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
if (init_mrk[i * m + j]) continue;
elms.clear();
init_dfs(i, j, c[i * m + j]);
comp new_comp;
new_comp.color = c[i * m + j];
new_comp.pnts = elms;
new_comp.large = 0;
new_comp.big_neib.clear();
new_comp.by_color.clear();
comps.PB(new_comp);
}
for (int i = 0; i < n * m; i++)
pre[i] = i;
for (int i = 0; i < sz(comps); i++)
if (sz(comps[i].pnts) > BLOCK)
declare_big(comps[i]);
}
void merge(int c1, int c2){
c1 = get_pre(c1);
c2 = get_pre(c2);
assert(c1 != c2);
if (sz(comps[c1].pnts) < sz(comps[c2].pnts))
swap(c1, c2);
comp &fi = comps[c1];
comp &se = comps[c2];
if (fi.large && !se.large)
declare_big(se);
if (se.large && !fi.large)
declare_big(fi);
{
/// update pnts
pre[c2] = c1;
for (i2 CR : se.pnts){
int x = CR[0], y = CR[1];
fi.pnts.PB(CR);
who[x * m + y] = c1;
}
vector<i2> ().swap(se.pnts);
}
{
/// update big_neib
vector<int> nw_big;
nw_big.clear();
tt++;
for (int cr : fi.big_neib){
cr = get_pre(cr);
if (used[cr] < tt) {
nw_big.PB(cr);
used[cr] = tt;
}
}
for (int cr : se.big_neib){
cr = get_pre(cr);
if (used[cr] < tt) {
nw_big.PB(cr);
used[cr] = tt;
}
}
vector<int> ().swap(fi.big_neib);
vector<int> ().swap(se.big_neib);
fi.big_neib.swap(nw_big);
}
if (fi.large) {
/// update by_color
if (sz(fi.by_color) < sz(se.by_color))
fi.by_color.swap(se.by_color);
for (auto cr : se.by_color){
int col = cr.ft;
vector<int> &sml = cr.sd;
vector<int> &big = fi.by_color[col];
if (sz(sml) > sz(big))
sml.swap(big);
for (int cr : sml)
big.PB(cr);
vector<int> ().swap(sml);
}
}
if (!fi.large && sz(fi.pnts) > BLOCK)
declare_big(fi);
}
void Fill(int x, int y, int nw_col){
int cur_comp = who[x * m + y];
comps[cur_comp].color = nw_col;
if (comps[cur_comp].large){
tt++;
vector<int> nw;
nw.clear();
used[cur_comp] = tt;
for (int co_id : comps[cur_comp].by_color[nw_col]){
co_id = get_pre(co_id);
if (used[co_id] < tt && comps[co_id].color == nw_col){
nw.PB(co_id);
used[co_id] = tt;
}
}
vector<int> ().swap(comps[cur_comp].by_color[nw_col]);
for (int ids : nw)
merge(cur_comp, ids);
} else {
tt++;
vector<int> nw;
nw.clear();
used[cur_comp] = tt;
for (i2 CR : comps[cur_comp].pnts){
int X = CR[0], Y = CR[1];
for (int it = 0; it < 4; it++){
int cx = X + stp[it][0];
int cy = Y + stp[it][1];
if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
int co_id = who[cx * m + cy];
if (used[co_id] < tt && comps[co_id].color == nw_col){
nw.PB(co_id);
used[co_id] = tt;
}
}
}
for (int ids : nw)
merge(cur_comp, ids);
}
/// traverse big_neib and change color
cur_comp = who[x * m + y];
int col = comps[cur_comp].color;
tt++;
used[cur_comp] = tt;
for (int cr : comps[cur_comp].big_neib){
cr = get_pre(cr);
if (used[cr] < tt) {
comps[cr].by_color[col].PB(cur_comp);
used[cr] = tt;
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
Init();
int qq; cin >> qq;
for (; qq; qq--){
int x, y, col; cin >> x >> y >> col; x--; y--;
Fill(x, y, col);
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
int co_id = who[i * m + j];
cout << comps[co_id].color << " ";
}
cout << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
2 ms |
972 KB |
Output is correct |
| 3 |
Correct |
16 ms |
9000 KB |
Output is correct |
| 4 |
Correct |
13 ms |
4684 KB |
Output is correct |
| 5 |
Correct |
19 ms |
5020 KB |
Output is correct |
| 6 |
Correct |
13 ms |
4812 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
35016 KB |
Output is correct |
| 2 |
Correct |
233 ms |
70008 KB |
Output is correct |
| 3 |
Correct |
291 ms |
81088 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
487 ms |
139304 KB |
Output is correct |
| 2 |
Correct |
462 ms |
139304 KB |
Output is correct |
| 3 |
Correct |
494 ms |
139168 KB |
Output is correct |
| 4 |
Correct |
485 ms |
139432 KB |
Output is correct |
| 5 |
Correct |
429 ms |
139436 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
321 ms |
74756 KB |
Output is correct |
| 2 |
Correct |
450 ms |
90176 KB |
Output is correct |
| 3 |
Correct |
673 ms |
97304 KB |
Output is correct |
| 4 |
Correct |
519 ms |
92060 KB |
Output is correct |
| 5 |
Correct |
692 ms |
103556 KB |
Output is correct |
| 6 |
Correct |
256 ms |
78516 KB |
Output is correct |
| 7 |
Correct |
227 ms |
72600 KB |
Output is correct |
| 8 |
Correct |
188 ms |
49728 KB |
Output is correct |
| 9 |
Correct |
653 ms |
93680 KB |
Output is correct |
