| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 576849 |
2022-06-13T16:18:43 Z |
PurpleCrayon |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
321164 KB |
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 998244353;
const int B = 430, K = N / B;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, p[N], sz[N];
int col[N];
unordered_map<int, unordered_set<int>> adj_col[N];
int find_set(int v) {
return v == p[v] ? v : p[v] = find_set(p[v]);
}
unordered_set<int> all_big;
void union_sets(int a, int b) { // merge, but only in the dsu
a = find_set(a), b = find_set(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a, sz[a] += sz[b], sz[b] = 0;
all_big.erase(b);
}
void union_big(int a, int b) { // just merge adj_col
a = find_set(a), b = find_set(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
for (auto& [k, v] : adj_col[b]) {
for (auto& x : v) adj_col[a][k].insert(x);
}
adj_col[b].clear();
}
int get_col(int v) {
return col[find_set(v)];
}
int tt = 0;
int vis[N], use[N];
vector<int> small_adj;
void dfs_small(int v) {
int i = v / m, j = v % m;
vis[v] = tt;
for (int k = 0; k < 4; k++) {
int ni = i + dx[k], nj = j + dy[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
if (vis[ni*m + nj] == tt) continue;
if (find_set(ni*m + nj) != find_set(v)) {
if (use[find_set(ni*m + nj)] != tt) {
small_adj.push_back(find_set(ni*m + nj));
use[find_set(ni*m + nj)] = tt;
}
} else {
dfs_small(ni*m + nj);
}
}
}
void make_big(int v) { // make information for v to be a big component
tt++;
small_adj.clear();
dfs_small(v);
all_big.insert(find_set(v));
for (auto nxt : small_adj) {
adj_col[find_set(v)][get_col(nxt)].insert(find_set(nxt));
}
}
void add_small(int v) { // add v to the info of all surrounding big components
tt++;
small_adj.clear();
dfs_small(v);
for (auto nxt : small_adj) {
if (sz[find_set(nxt)] >= B) {
adj_col[find_set(nxt)][get_col(v)].insert(find_set(v));
}
}
}
void clear_comp(int v) { // remove v from the info of all surrounding big components
for (auto nxt : all_big) {
adj_col[nxt][get_col(v)].erase(find_set(v));
}
}
void upd_big(int v, int x) {
v = find_set(v);
auto to_merge = adj_col[v][x];
for (auto nxt : to_merge) {
clear_comp(nxt);
}
clear_comp(v);
for (auto nxt : to_merge) {
if (sz[find_set(nxt)] < B) {
make_big(nxt);
}
union_big(v, nxt);
union_sets(v, nxt);
}
col[find_set(v)] = x;
for (auto nxt : all_big) if (adj_col[v][get_col(nxt)].find(nxt) != adj_col[v][get_col(nxt)].end()) {
adj_col[nxt][get_col(v)].insert(v);
}
}
void upd_small(int v, int x) {
tt++;
small_adj.clear();
dfs_small(v);
int new_size = sz[find_set(v)];
for (auto nxt : small_adj) if (get_col(nxt) == x) {
new_size += sz[find_set(nxt)];
}
if (new_size >= B) {
make_big(v);
upd_big(v, x);
} else {
clear_comp(v);
for (auto add : small_adj) {
if (get_col(add) == x) {
clear_comp(add);
}
}
for (auto add : small_adj) {
if (get_col(add) == x) {
union_sets(v, add);
}
}
col[find_set(v)] = x;
add_small(v);
}
}
void upd(int i, int j, int x) {
int v = i*m + j;
if (sz[find_set(v)] >= B) upd_big(v, x);
else upd_small(v, x);
}
int a[N];
void init() { // initially merge stuff
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
p[i*m + j] = i*m + j;
sz[i*m + j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i*m + j];
col[i*m + j] = a[i*m + j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 4; k++) {
int ni = i + dx[k], nj = j + dy[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
if (a[ni*m + nj] == a[i*m + j]) {
union_sets(i*m + j, ni*m + nj);
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (p[i*m + j] == i*m + j && sz[find_set(i*m + j)] >= B) {
make_big(i*m + j);
}
}
}
}
void solve() {
cin >> n >> m;
init();
int q; cin >> q;
while (q--) {
int i, j, x; cin >> i >> j >> x, --i, --j;
upd(i, j, x);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << col[find_set(i*m + j)] << ' ';
cout << '\n';
}
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11220 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11348 KB |
Output is correct |
| 3 |
Correct |
10 ms |
11568 KB |
Output is correct |
| 4 |
Correct |
14 ms |
11604 KB |
Output is correct |
| 5 |
Correct |
16 ms |
13232 KB |
Output is correct |
| 6 |
Correct |
16 ms |
11856 KB |
Output is correct |
| 7 |
Correct |
6 ms |
11220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
12608 KB |
Output is correct |
| 2 |
Correct |
189 ms |
14352 KB |
Output is correct |
| 3 |
Correct |
199 ms |
39288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
33504 KB |
Output is correct |
| 2 |
Correct |
192 ms |
26528 KB |
Output is correct |
| 3 |
Correct |
244 ms |
31880 KB |
Output is correct |
| 4 |
Correct |
313 ms |
25488 KB |
Output is correct |
| 5 |
Correct |
265 ms |
24444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
18320 KB |
Output is correct |
| 2 |
Correct |
302 ms |
41164 KB |
Output is correct |
| 3 |
Execution timed out |
3097 ms |
321164 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
