| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 420911 |
2021-06-08T14:51:00 Z |
two_sides |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
219100 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MAXC = 105;
const size_t MAXS = 5;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
int N, M;
bool vis[MAXN];
#define valid(x, y) (x) >= 0 && (x) < N && (y) >= 0 && (y) < M
#define flat(x, y) (x) * M + (y)
#define comps(x, y) comps[flat(x, y)]
struct component {
int col, idx;
vector <int> big;
vector <vector <int>> grp;
vector <pair <int, int>> cell;
} comps[MAXN];
int getCol(int u) {
return comps[comps[u].idx].col;
}
int getCol(int x, int y) {
return getCol(flat(x, y));
}
vector <int> get(component &a, int col) {
static int x, y;
static vector <int> res;
res.clear();
if (a.cell.size() >= MAXS) {
for (int x : a.grp[col]) {
x = comps[x].idx;
if (comps[x].col == col)
res.push_back(x);
}
a.grp[col].clear();
return res;
}
if (col) {
for (auto pp : a.cell) {
tie(x, y) = pp;
for (int k = 0; k < 4; k++)
if (valid(x + dx[k], y + dy[k]) &&
getCol(x + dx[k], y + dy[k]) == col)
res.push_back(comps(x + dx[k], y + dy[k]).idx);
}
} else {
for (auto pp : a.cell) {
tie(x, y) = pp;
for (int k = 0; k < 4; k++)
if (valid(x + dx[k], y + dy[k]) &&
getCol(x + dx[k], y + dy[k]) != a.col)
res.push_back(comps(x + dx[k], y + dy[k]).idx);
}
}
return res;
}
template <class T>
void destroy(vector <T> &v) {
v.clear();
v.shrink_to_fit();
}
bool join(int u, int v) {
static vector <int> tmp;
u = comps[u].idx; v = comps[v].idx;
if (u == v) return false;
if (comps[u].cell.size() < comps[v].cell.size())
swap(u, v);
component &a = comps[u];
component &b = comps[v];
if (a.cell.size() < MAXS) {
if (a.cell.size() + b.cell.size() >= MAXS) {
tmp = get(a, 0);
a.grp.resize(MAXC);
for (int x : tmp) {
a.grp[comps[x].col].push_back(x);
comps[x].big.push_back(u);
}
tmp = get(b, 0);
for (int x : tmp) {
a.grp[comps[x].col].push_back(x);
comps[x].big.push_back(u);
}
assert(a.grp.size());
}
} else if (b.cell.size() < MAXS) {
assert(a.grp.size());
tmp = get(b, 0);
for (int x : tmp) {
a.grp[comps[x].col].push_back(x);
comps[x].big.push_back(u);
}
} else {
for (int c = 1; c < MAXC; c++) {
if (a.grp[c].size() < b.grp[c].size())
swap(a.grp[c], b.grp[c]);
for (int x : b.grp[c])
a.grp[c].push_back(x);
}
}
for (auto pp : b.cell) {
a.cell.push_back(pp);
comps(pp.first, pp.second).idx = u;
}
for (auto x : b.big)
a.big.push_back(comps[x].idx);
for (auto x : a.big) {
x = comps[x].idx;
comps[x].grp[a.col].push_back(u);
}
destroy(b.cell);
destroy(b.big);
destroy(b.grp);
return true;
}
void print() {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cout << getCol(i, j) << " \n"[j == M - 1];
cout << "\n";
}
int main() {
//cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
vector <vector <int>> S(N, vector <int> (M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> S[i][j];
queue <pair <int, int>> que;
vector <int> big;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
if (vis[flat(i, j)]) continue;
que.emplace(i, j); int x, y;
vis[flat(i, j)] = true;
comps(i, j).col = S[i][j] + 1;
while (que.size()) {
tie(x, y) = que.front(); que.pop();
comps(i, j).cell.emplace_back(x, y);
comps(x, y).idx = flat(i, j);
for (int k = 0; k < 4; k++)
if (valid(x + dx[k], y + dy[k]) &&
!vis[flat(x + dx[k], y + dy[k])] &&
S[x + dx[k]][y + dy[k]] == S[i][j]) {
vis[flat(x + dx[k], y + dy[k])] = true;
que.emplace(x + dx[k], y + dy[k]);
}
}
if (comps(i, j).cell.size() >= MAXS)
big.push_back(flat(i, j));
}
for (int u : big) {
vector <int> neighbor; int x, y;
for (auto pp : comps[u].cell) {
tie(x, y) = pp;
for (int k = 0; k < 4; k++)
if (valid(x + dx[k], y + dy[k]) &&
getCol(x + dx[k], y + dy[k]) != comps[u].col)
neighbor.push_back(comps(x + dx[k], y + dy[k]).idx);
}
comps[u].grp.resize(MAXC);
for (int x : neighbor) {
comps[u].grp[comps[x].col].push_back(x);
comps[x].big.push_back(u);
}
}
int Q; cin >> Q; int currrr = 0;
while (Q--) {
int x, y, col; cin >> x >> y >> col;
x--; y--; col++;
int u = comps(x, y).idx;
if (col == comps[u].col) continue;
comps[u].col = col;
vector <int> neighbor = get(comps[u], col);
for (int v : neighbor) join(u, v);
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cout << getCol(i, j) - 1 << " \n"[j == M - 1];
}
Compilation message
paint.cpp: In function 'int main()':
paint.cpp:184:26: warning: unused variable 'currrr' [-Wunused-variable]
184 | int Q; cin >> Q; int currrr = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
16052 KB |
Output is correct |
| 2 |
Correct |
10 ms |
16076 KB |
Output is correct |
| 3 |
Correct |
20 ms |
16460 KB |
Output is correct |
| 4 |
Incorrect |
21 ms |
17088 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
23604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3092 ms |
219100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
36828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
