| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 467272 |
2021-08-22T11:20:49 Z |
phathnv |
Paint (COI20_paint) |
C++11 |
|
10 ms |
14460 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200000;
const int BLOCKSIZE = 444;
int m, n, q, curInd;
vector<vector<int>> ind;
vector<int> adj[N];
set<pair<int, int>> s[N];
int root[N], sz[N], col[N];
int FindRoot(int u) {
if (u == root[u])
return u;
return root[u] = FindRoot(root[u]);
}
void Update(int u, int type) {
u = FindRoot(u);
if (sz[u] < BLOCKSIZE)
return;
for (int v : adj[u]) {
v = FindRoot(v);
if (sz[v] >= BLOCKSIZE) {
if (type == -1)
s[v].erase({col[u], u});
else
s[v].insert({col[u], u});
}
}
}
void Merge(int u, int v) {
u = FindRoot(u);
v = FindRoot(v);
if (u == v || col[u] != col[v])
return;
//assert(col[u] == col[v]);
Update(u, -1);
Update(v, -1);
if (sz[u] < sz[v])
swap(u, v);
if (s[u].size() < s[v].size())
swap(s[u], s[v]);
for (int x : adj[v])
adj[u].push_back(x);
adj[v].clear();
for (auto p : s[v])
s[u].insert(p);
s[v].clear();
root[v] = u;
sz[u] += sz[v];
if (sz[u] >= BLOCKSIZE && sz[u] - sz[v] < BLOCKSIZE) {
vector<int> newAdj;
for (int v : adj[u]) {
v = FindRoot(v);
if (v == u)
continue;
if (sz[v] >= BLOCKSIZE) {
newAdj.push_back(v);
adj[v].push_back(u);
} else {
s[u].insert({col[v], v});
}
}
adj[u] = newAdj;
}
Update(u, 1);
}
void Color(int u, int c) {
u = FindRoot(u);
Update(u, -1);
col[u] = c;
Update(u, 1);
vector<pair<int, int>> shouldMerge, shouldDel;
for (int v : adj[u]) {
v = FindRoot(v);
if (col[v] == c)
shouldMerge.push_back({u, v});
}
auto it = s[u].lower_bound({c, -1});
while (it != s[u].end()) {
if ((*it).first > c)
break;
int v = (*it).second;
shouldMerge.push_back({u, v});
shouldDel.push_back(*it);
++it;
}
for (auto p : shouldDel)
s[u].erase(p);
for (auto p : shouldMerge)
Merge(p.first, p.second);
}
int main() {
freopen("inp.txt", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
ind.assign(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
ind[i][j] = curInd++;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i + 1 < m) {
adj[ind[i][j]].push_back(ind[i + 1][j]);
adj[ind[i + 1][j]].push_back(ind[i][j]);
}
if (j + 1 < n) {
adj[ind[i][j]].push_back(ind[i][j + 1]);
adj[ind[i][j + 1]].push_back(ind[i][j]);
}
}
for (int i = 0; i < m * n; i++) {
root[i] = i;
sz[i] = 1;
col[i] = -1;
}
for (int u = 0; u < m * n; u++) {
int c;
cin >> c;
Color(u, c);
}
cin >> q;
while (q--) {
int x, y, c;
cin >> x >> y >> c;
x--, y--;
Color(ind[x][y], c);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
cout << col[FindRoot(ind[i][j])] << ' ';
cout << '\n';
}
return 0;
}
Compilation message
paint.cpp: In function 'int main()':
paint.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("inp.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
