// source: https://oj.uz/problem/view/COI20_paint
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN = 300000;
const int K = 350;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
vector<vector<int>> grid;
vector<vector<bool>> vis;
vector<vector<int>> comp_id;
int comp_vis[mxN];
int comp_tracker = 0;
int n, m;
struct Component {
int id;
int color;
bool large;
vector<pair<int, int>> pixels;
vector<int> larges;
map<int, vector<int>> by_color;
};
vector<Component> C;
int parent[mxN];
int get_par(int id) {
return id == parent[id] ? id : parent[id] = get_par(parent[id]);
}
void trav_neighbors(int id, function<void(int)> f) {
++comp_tracker;
for (pair<int, int> cell : C[id].pixels) {
for (int k = 0; k < 4; ++k) {
int a = cell.first + dx[k];
int b = cell.second + dy[k];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
int nid = comp_id[a][b];
if (id != nid && comp_vis[nid] != comp_tracker) {
comp_vis[nid] = comp_tracker;
f(nid);
}
}
}
}
vector<int> get_neighbors(int id, int color) {
vector<int> ret;
Component& comp = C[id];
if (comp.large) {
++comp_tracker;
for (int x : comp.by_color[color]) {
int nid = get_par(x);
if (id != nid && comp_vis[nid] != comp_tracker && C[nid].color == color) {
comp_vis[nid] = comp_tracker;
ret.push_back(nid);
}
}
comp.by_color.erase(color); // save memory
}
else {
trav_neighbors(id, [&ret, color](int nid) {
if (color == C[nid].color) ret.push_back(nid);
});
}
return ret;
}
void declare_large(int id) {
C[id].large = 1;
trav_neighbors(id, [id](int nid) {
C[nid].larges.push_back(id);
C[id].by_color[C[nid].color].push_back(nid);
});
}
void trav_larges(int id, function<void(int)> f) {
++comp_tracker;
for (int x : C[id].larges) {
int nid = get_par(x);
if (id != nid && comp_vis[nid] != comp_tracker) {
comp_vis[nid] = comp_tracker;
f(nid);
}
}
}
void remake_larges(int id) {
vector<int> new_larges;
trav_larges(id, [&new_larges](int nid) {
new_larges.push_back(nid);
});
C[id].larges.swap(new_larges);
}
int Merge(int a, int b) { // merge b into a
assert(a != b);
if (C[a].pixels.size() < C[b].pixels.size()) swap(a, b);
if (C[a].large && !C[b].large) declare_large(b);
parent[b] = a;
for (pair<int, int> x : C[b].pixels) {
comp_id[x.first][x.second] = a;
C[a].pixels.push_back(x);
}
vector<pair<int, int>>().swap(C[b].pixels);
if (C[a].larges.size() < C[b].larges.size()) swap(C[a].larges, C[b].larges);
for (int x : C[b].larges) C[a].larges.push_back(x);
vector<int>().swap(C[b].larges);
remake_larges(a);
if (C[a].by_color.size() < C[b].by_color.size()) swap(C[a].by_color, C[b].by_color);
for (auto& entry : C[b].by_color) {
int color = entry.first;
vector<int>& lista = C[a].by_color[color];
vector<int>& listb = entry.second;
if (lista.size() < listb.size()) swap(lista, listb);
for (int x : listb) lista.push_back(x);
}
map<int, vector<int>>().swap(C[b].by_color);
if (!C[a].large && C[a].pixels.size() > K) {
declare_large(a);
}
//cerr << "successfully merged " << a << " and " << b << "\n";
return a;
}
void fill(int i, int j, int color) {
int id = comp_id[i][j];
C[id].color = color;
for (int nid : get_neighbors(id, color)) {
id = Merge(id, nid);
}
trav_larges(id, [id, color](int nid) {
C[nid].by_color[color].push_back(id);
});
}
/////////////////////////////////// Some initialization
vector<pair<int, int>> traversal;
void dfs_for_component(int i, int j) {
vis[i][j] = 1;
comp_id[i][j] = C.size();
traversal.emplace_back(i, j);
for (int k = 0; k < 4; ++k) {
int a = i + dx[k];
int b = j + dy[k];
if (0 <= a && a < n && 0 <= b && b < m && !vis[a][b] && grid[i][j] == grid[a][b]) {
dfs_for_component(a, b);
}
}
}
void init() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (vis[i][j]) continue;
Component cur;
dfs_for_component(i, j);
cur.id = C.size();
cur.color = grid[i][j];
cur.large = 0;
swap(traversal, cur.pixels);
C.push_back(cur);
}
}
for (Component& c : C) {
if (c.pixels.size() > K) {
declare_large(c.id);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
grid = vector<vector<int>>(n, vector<int>(m));
vis = vector<vector<bool>>(n, vector<bool>(m));
comp_id = vector<vector<int>>(n, vector<int>(m));
iota(parent, parent + n * m, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
init();
//cerr << "Reached\n";
int q; cin >> q;
while(q--) {
int i, j, color; cin >> i >> j >> color, --i, --j;
fill(i, j, color);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (j) cout << " ";
cout << C[comp_id[i][j]].color;
}
cout << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
620 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2564 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1540 KB |
Output is correct |
| 5 |
Correct |
12 ms |
2180 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
9208 KB |
Output is correct |
| 2 |
Correct |
144 ms |
18068 KB |
Output is correct |
| 3 |
Correct |
230 ms |
29112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
35572 KB |
Output is correct |
| 2 |
Correct |
203 ms |
35828 KB |
Output is correct |
| 3 |
Correct |
227 ms |
36284 KB |
Output is correct |
| 4 |
Correct |
242 ms |
35716 KB |
Output is correct |
| 5 |
Correct |
215 ms |
35612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
20956 KB |
Output is correct |
| 2 |
Correct |
508 ms |
30472 KB |
Output is correct |
| 3 |
Correct |
981 ms |
35416 KB |
Output is correct |
| 4 |
Correct |
585 ms |
29792 KB |
Output is correct |
| 5 |
Correct |
937 ms |
39080 KB |
Output is correct |
| 6 |
Correct |
179 ms |
23708 KB |
Output is correct |
| 7 |
Correct |
175 ms |
20024 KB |
Output is correct |
| 8 |
Correct |
169 ms |
16912 KB |
Output is correct |
| 9 |
Correct |
819 ms |
33636 KB |
Output is correct |
