| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1043780 |
2024-08-04T17:05:54 Z |
fryingduc |
Paint (COI20_paint) |
C++17 |
|
1040 ms |
41248 KB |
#include "bits/stdc++.h"
using namespace std;
const int maxn = 2e5 + 5;
const int C = 1e5 + 5;
const int B = 300;
int n, m, q;
vector<vector<int>> a, id, vis;
const int movex[] = {1, -1, 0, 0};
const int movey[] = {0, 0, 1, -1};
int total;
bool flip;
vector<int> g[maxn];
int color[maxn];
map<int, vector<int>> mp[maxn];
struct dsu {
int n;
vector<int> par, sz;
dsu() {}
dsu(int n) : n(n), par(n + 5), sz(n + 5) {
for(int i = 0; i <= n; ++i) {
par[i] = i;
sz[i] = 1;
color[i] = -1;
}
}
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
for(auto it:mp[v]) {
for(auto i:it.second) {
mp[u][it.first].push_back(i);
}
}
mp[v].clear();
par[v] = u;
if(sz[u] > B) {
for(auto i:g[v]) {
i = find(i);
if(i == u) continue;
if(sz[i] > B) {
g[u].push_back(i);
if(sz[v] <= B)
g[i].push_back(u);
}
else {
mp[u][color[i]].push_back(i);
}
}
}
else if(sz[u] + sz[v] > B) {
vector<int> adj;
int cur_ver = u;
for(int ite = 0; ite < 2; ++ite) {
for(auto i:g[cur_ver]) {
i = find(i);
if(i == u) continue;
if(sz[i] > B) {
adj.push_back(i);
g[i].push_back(u);
}
else {
mp[u][color[i]].push_back(i);
}
}
cur_ver = v;
}
g[u] = adj;
}
else {
for(auto i:g[v]) {
i = find(i);
g[u].push_back(i);
}
for(auto i:g[u]) {
i = find(i);
if(sz[i] > B) mp[i][color[u]].push_back(u);
}
}
sz[u] += sz[v];
g[v].clear();
}
bool is_joined(int u, int v) {
return find(u) == find(v);
}
} d;
void undo_small(int x, int y, int c) {
queue<pair<int, int>> q;
q.push({x, y});
vis[x][y] = 0;
color[d.find(id[x][y])] = c;
while(!q.empty()) {
int u = q.front().first, v = q.front().second;
q.pop();
for(int move = 0; move < 4; ++move) {
int i = movex[move] + u, j = movey[move] + v;
if(i > n || j > m || i < 1 || j < 1 || !vis[i][j]) continue;
if(vis[i][j]) {
vis[i][j] = 0;
q.push({i, j});
}
}
}
}
void color_small(int x, int y, int c) {
queue<pair<int, int>> q;
q.push({x, y});
vis[x][y] = 1;
color[d.find(id[x][y])] = c;
while(!q.empty()) {
int u = q.front().first, v = q.front().second;
q.pop();
for(int move = 0; move < 4; ++move) {
int i = movex[move] + u, j = movey[move] + v;
if(i > n || j > m || i < 1 || j < 1 || vis[i][j]) continue;
if(d.find(id[i][j]) == d.find(id[x][y])) {
vis[i][j] = 1;
q.push({i, j});
}
else if(color[d.find(id[i][j])] == c) {
d.join(id[x][y], id[u][v]);
}
}
}
undo_small(x, y, c);
}
void add_edge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void query(int u, int c) {
vector<int> adjj;
u = d.find(u);
color[u] = c;
for(auto v:g[u]) {
v = d.find(v);
if(color[v] == color[u]) {
adjj.push_back(v);
}
}
if(mp[u].find(c) != mp[u].end()) {
vector<int> &now = mp[u][c];
for(auto v:now) {
v = d.find(v);
if(color[v] == color[u]) {
adjj.push_back(v);
}
}
mp[u].erase(c);
}
for(auto v:adjj) {
d.join(u, v);
}
u = d.find(u);
if(d.sz[u] <= B) {
for(auto v:g[u]) {
v = d.find(v);
if(d.sz[v] > B) {
mp[v][color[u]].push_back(u);
}
}
}
}
void solve() {
cin >> n >> m;
a.resize(n + 5, vector<int>(m + 5));
id.resize(n + 5, vector<int>(m + 5));
vis.resize(n + 5, vector<int>(m + 5));
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> a[i][j];
id[i][j] = ++total;
}
}
d = dsu(total + 5);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(i < n) {
add_edge(id[i][j], id[i + 1][j]);
}
if(j < m) {
add_edge(id[i][j], id[i][j + 1]);
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
query(id[i][j], a[i][j]);
}
}
cin >> q;
while(q--) {
int x, y, c; cin >> x >> y >> c;
query(id[x][y], c);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cout << color[d.find(id[i][j])] << ' ';
}
cout << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#define task "paint"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
solve();
return 0;
}
/*
4 4
1 0 1 3
1 3 2 2
3 3 1 2
2 2 1 3
3
1 2 3
3 2 1
4 2 3
6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1
4
6 2 2
3 5 2
3 2 3
1 2 3
6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1
2
6 2 2
6 2 3
4 2
0 0
1 1
0 0
3 3
3
2 1 0
1 1 5
4 1 7
3 2
0 0
1 1
0 0
1
2 1 0
2 3
0 0 0
1 1 1
2
2 1 0
1 1 5
*/
Compilation message
paint.cpp: In function 'int main()':
paint.cpp:231:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
231 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:232:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
232 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15452 KB |
Output is correct |
| 3 |
Correct |
5 ms |
15704 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15708 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16476 KB |
Output is correct |
| 6 |
Correct |
14 ms |
16220 KB |
Output is correct |
| 7 |
Correct |
2 ms |
15196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
21096 KB |
Output is correct |
| 2 |
Correct |
97 ms |
28936 KB |
Output is correct |
| 3 |
Correct |
65 ms |
41248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
27216 KB |
Output is correct |
| 2 |
Correct |
62 ms |
27728 KB |
Output is correct |
| 3 |
Correct |
67 ms |
27984 KB |
Output is correct |
| 4 |
Correct |
117 ms |
30288 KB |
Output is correct |
| 5 |
Correct |
115 ms |
29824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
25684 KB |
Output is correct |
| 2 |
Correct |
244 ms |
39624 KB |
Output is correct |
| 3 |
Correct |
1040 ms |
37072 KB |
Output is correct |
| 4 |
Correct |
467 ms |
37220 KB |
Output is correct |
| 5 |
Correct |
357 ms |
35356 KB |
Output is correct |
| 6 |
Correct |
92 ms |
31516 KB |
Output is correct |
| 7 |
Correct |
94 ms |
31460 KB |
Output is correct |
| 8 |
Correct |
93 ms |
31572 KB |
Output is correct |
| 9 |
Correct |
406 ms |
37968 KB |
Output is correct |
