| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 678366 |
2023-01-05T16:12:49 Z |
Cyanmond |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
300100 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 = 600, 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::vector<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))].push_back(uft.find(get_id(nx, ny)));
}
}
}
}
std::vector<std::vector<std::unordered_set<int>>> gb(R * S);
std::vector<std::vector<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].push_back(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)].push_back(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)].push_back(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);
std::copy(large_list[b].begin(), large_list[b].end(), std::back_inserter(large_list[a]));
};
auto merge_small = [&](int a, int b) {
if (uft.size(a) < uft.size(b)) {
std::swap(a, b);
}
uft.unite(a, b);
std::copy(graph[b].begin(), graph[b].end(), std::back_inserter(graph[a]));
std::copy(large_list[b].begin(), large_list[b].end(), std::back_inserter(large_list[a]));
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 |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1420 KB |
Output is correct |
| 4 |
Correct |
12 ms |
6940 KB |
Output is correct |
| 5 |
Correct |
220 ms |
8048 KB |
Output is correct |
| 6 |
Correct |
702 ms |
12756 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
7280 KB |
Output is correct |
| 2 |
Correct |
479 ms |
300100 KB |
Output is correct |
| 3 |
Execution timed out |
3073 ms |
28764 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3089 ms |
59512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
36880 KB |
Output is correct |
| 2 |
Execution timed out |
3099 ms |
42588 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
