Submission #584845

#TimeUsernameProblemLanguageResultExecution timeMemory
584845eecsPaint (COI20_paint)C++17
48 / 100
988 ms524288 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 200010, B = 500; int r, c, q, bel[maxn], col[maxn]; vector<int> V[maxn], adj[maxn]; vector<unordered_set<int>> S[maxn]; bool mark[maxn]; set<int> big; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> r >> c; for (int i = 0; i < r * c; i++) { cin >> col[i]; bel[i] = i, V[i] = {i}; } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { for (auto dir : {array<int, 2>{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) { int x = i + dir[0], y = j + dir[1]; if (!~x || x == r || !~y || y == c) continue; adj[i * c + j].push_back(x * c + y); } } } auto merge = [&](int u, int v) { if (V[u].size() < V[v].size()) swap(u, v); if (V[u].size() < B && V[u].size() + V[v].size() >= B) { S[u].resize(1e5), big.insert(u); for (int x : adj[u]) S[u][col[bel[x]]].insert(bel[x]); } if (V[u].size() + V[v].size() >= B) { for (int x : adj[v]) S[u][col[bel[x]]].insert(bel[x]); S[v].clear(), S[v].shrink_to_fit(), big.erase(v); } for (int x : V[v]) bel[x] = u; copy(V[v].begin(), V[v].end(), back_inserter(V[u])); copy(adj[v].begin(), adj[v].end(), back_inserter(adj[u])); }; auto fill = [&](int u, int x) { u = bel[u]; while (1) { if (S[u].size() < B) { bool flag = 0; auto tmp = adj[u]; for (int v : tmp) { v = bel[v]; if (u ^ v && col[v] == x) merge(u, v), flag = 1, u = bel[u]; } if (!flag) break; } else { if (S[u][x].empty()) break; int v = *S[u][x].begin(); S[u][x].erase(v), v = bel[v]; if (u ^ v && col[v] == x) merge(u, v), u = bel[u]; } } col[u] = x; if (S[u].size() < B) { vector<int> _adj; for (int v : adj[u]) { v = bel[v]; if (u ^ v && !mark[v]) _adj.push_back(v), mark[v] = 1; } adj[u] = _adj; for (int v : big) { if (mark[v]) S[v][col[u]].insert(u); } for (int v : adj[u]) mark[v] = 0; } else { for (int v : big) { if (u ^ v && S[u][col[v]].count(v)) S[v][col[u]].insert(u); } } }; for (int i = 0; i < r * c; i++) { fill(i, col[i]); } cin >> q; while (q--) { int i, j, x; cin >> i >> j >> x; fill(--i * c + --j, x); } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cout << col[bel[i * c + j]] << " "; } cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...