| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 678368 |
2023-01-05T16:18:27 Z |
Cyanmond |
Paint (COI20_paint) |
C++17 |
|
871 ms |
251352 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)) << (j == S - 1 ? '\n' : ' ');
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
3 ms |
724 KB |
Output is correct |
| 3 |
Correct |
16 ms |
4132 KB |
Output is correct |
| 4 |
Correct |
27 ms |
9044 KB |
Output is correct |
| 5 |
Correct |
21 ms |
10068 KB |
Output is correct |
| 6 |
Correct |
16 ms |
8916 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
17404 KB |
Output is correct |
| 2 |
Correct |
321 ms |
200728 KB |
Output is correct |
| 3 |
Correct |
286 ms |
70980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
110996 KB |
Output is correct |
| 2 |
Correct |
354 ms |
108732 KB |
Output is correct |
| 3 |
Correct |
387 ms |
147432 KB |
Output is correct |
| 4 |
Correct |
511 ms |
249700 KB |
Output is correct |
| 5 |
Correct |
440 ms |
221804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
70232 KB |
Output is correct |
| 2 |
Correct |
465 ms |
88876 KB |
Output is correct |
| 3 |
Correct |
846 ms |
235288 KB |
Output is correct |
| 4 |
Correct |
871 ms |
251352 KB |
Output is correct |
| 5 |
Correct |
870 ms |
132652 KB |
Output is correct |
| 6 |
Correct |
419 ms |
223820 KB |
Output is correct |
| 7 |
Correct |
352 ms |
171792 KB |
Output is correct |
| 8 |
Correct |
324 ms |
132960 KB |
Output is correct |
| 9 |
Correct |
769 ms |
88604 KB |
Output is correct |
