| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 714049 |
2023-03-23T17:30:06 Z |
Bliznetc |
Paint (COI20_paint) |
C++17 |
|
873 ms |
251588 KB |
#include <bits/stdc++.h>
constexpr std::array<std::pair<int, int>, 4> dxy = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr int B = 1000, H = 100000;
struct UnionFind {
int n;
std::vector<int> tree, color;
UnionFind(int n_) {
n = n_;
tree.assign(n, -1);
color.assign(n, 0);
}
int find(int v) {
if (tree[v] < 0) {
return v;
} else {
return tree[v] = find(tree[v]);
}
}
int size(int v) {
return -tree[find(v)];
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (size(a) < size(b)) {
std::swap(a, b);
}
tree[a] += tree[b];
tree[b] = a;
}
int get_color(int v) {
return color[find(v)];
}
void set_color(int v, int c) {
color[find(v)] = c;
}
};
int main() {
int R, S;
std::cin >> R >> S;
std::vector<std::vector<int>> C(R, std::vector<int>(S));
for (auto &vec : C) {
for (auto &e : vec) {
std::cin >> e;
}
}
int Q;
std::cin >> Q;
std::vector<int> r(Q), s(Q), c(Q);
for (int i = 0; i < Q; ++i) {
std::cin >> r[i] >> s[i] >> c[i];
--r[i], --s[i];
}
auto get_id = [&](int x, int y) {
return x * S + y;
};
UnionFind uft(R * S);
for (int i = 0; i < R; ++i) {
for (int j = 0; j < S; ++j) {
uft.set_color(get_id(i, j), C[i][j]);
for (const auto &[ax, ay] : dxy) {
const int nx = i + ax, ny = j + ay;
if (nx < 0 or ny < 0 or nx >= R or ny >= S) {
continue;
}
if (C[i][j] == C[nx][ny]) {
uft.unite(get_id(i, j), get_id(nx, ny));
}
}
}
}
std::vector<std::unordered_set<int>> graph(R * S);
for (int i = 0; i < R; ++i) {
for (int j = 0; j < S; ++j) {
for (const auto &[ax, ay] : dxy) {
const int nx = i + ax, ny = j + ay;
if (nx < 0 or ny < 0 or nx >= R or ny >= S) {
continue;
}
if (C[i][j] != C[nx][ny]) {
graph[uft.find(get_id(i, j))].insert(uft.find(get_id(nx, ny)));
}
}
}
}
std::vector<std::vector<std::unordered_set<int>>> gb(R * S);
std::vector<std::unordered_set<int>> large_list(R * S);
for (int i = 0; i < R * S; ++i) {
if (uft.find(i) == i and uft.size(i) >= B) {
gb[i].resize(H);
for (const int t : graph[i]) {
large_list[t].insert(i);
gb[i][uft.get_color(t)].insert(t);
}
}
}
auto inc_block = [&](int v) {
assert(uft.size(v) >= B);
gb[v].resize(H);
for (const int t : graph[v]) {
large_list[uft.find(t)].insert(v);
gb[v][uft.get_color(t)].insert(uft.find(t));
}
};
auto merge_large = [&](int a, int b) {
if (uft.size(a) < uft.size(b)) {
std::swap(a, b);
}
if (uft.size(b) < B) {
for (const int t : graph[b]) {
const int v = uft.find(t);
gb[a][uft.get_color(v)].insert(v);
large_list[uft.find(t)].insert(a);
}
} else {
for (int i = 0; i < H; ++i) {
for (const int e : gb[b][i]) {
gb[a][i].insert(uft.find(e));
}
}
}
uft.unite(a, b);
for (const int e : large_list[b]) {
large_list[a].insert(uft.find(e));
}
};
auto merge_small = [&](int a, int b) {
if (uft.size(a) < uft.size(b)) {
std::swap(a, b);
}
uft.unite(a, b);
for (const int e : graph[b]) {
graph[a].insert(uft.find(e));
}
for (const int e : large_list[b]) {
large_list[a].insert(uft.find(e));
}
if (uft.size(a) >= B) {
inc_block(a);
}
};
auto merge = [&](int a, int b) {
a = uft.find(a);
b = uft.find(b);
if (a == b) {
return;
}
if (std::max(uft.size(a), uft.size(b)) >= B) {
merge_large(a, b);
} else {
merge_small(a, b);
}
};
for (int i = 0; i < Q; ++i) {
const int x = r[i], y = s[i];
const int v = uft.find(get_id(x, y));
uft.set_color(v, c[i]);
if (uft.size(v) >= B) {
auto g = gb[v][c[i]];
gb[v][c[i]].clear();
for (const int t : g) {
if (uft.get_color(t) != c[i]) {
continue;
}
if (uft.find(v) == uft.find(t)) {
continue;
} else {
merge(v, t);
}
}
} else {
auto cp = graph[v];
for (const int t : cp) {
if (uft.get_color(t) == c[i] and uft.find(v) != uft.find(t)) {
merge(v, t);
}
}
}
for (const int t : large_list[uft.find(v)]) {
gb[uft.find(t)][uft.get_color(v)].insert(uft.find(v));
}
}
for (int i = 0; i < R; ++i) {
for (int j = 0; j < S; ++j) {
std::cout << uft.get_color(get_id(i, j)) << " ";
}
std::cout << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4108 KB |
Output is correct |
| 4 |
Correct |
19 ms |
9044 KB |
Output is correct |
| 5 |
Correct |
21 ms |
10196 KB |
Output is correct |
| 6 |
Correct |
17 ms |
8912 KB |
Output is correct |
| 7 |
Correct |
1 ms |
300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
17512 KB |
Output is correct |
| 2 |
Correct |
321 ms |
201992 KB |
Output is correct |
| 3 |
Correct |
266 ms |
73288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
337 ms |
111216 KB |
Output is correct |
| 2 |
Correct |
319 ms |
109324 KB |
Output is correct |
| 3 |
Correct |
358 ms |
148072 KB |
Output is correct |
| 4 |
Correct |
471 ms |
250564 KB |
Output is correct |
| 5 |
Correct |
436 ms |
222648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
70164 KB |
Output is correct |
| 2 |
Correct |
454 ms |
90692 KB |
Output is correct |
| 3 |
Correct |
866 ms |
237168 KB |
Output is correct |
| 4 |
Correct |
867 ms |
251588 KB |
Output is correct |
| 5 |
Correct |
873 ms |
132812 KB |
Output is correct |
| 6 |
Correct |
385 ms |
223872 KB |
Output is correct |
| 7 |
Correct |
341 ms |
171812 KB |
Output is correct |
| 8 |
Correct |
314 ms |
132936 KB |
Output is correct |
| 9 |
Correct |
692 ms |
88488 KB |
Output is correct |
