Submission #1191665

#TimeUsernameProblemLanguageResultExecution timeMemory
1191665nhq0914Paint (COI20_paint)C++17
0 / 100
79 ms35512 KiB
#include <bits/stdc++.h> #define ord(i, j) ((i) * m + (j)) #define N(a) (int)a.size() #define FO(i, a, b) for(int i = (a); i <= (b); ++i) #define RE(i, a, b) for(int i = (a); i >= (b); --i) using namespace std; const int maxn = 2e5 + 1, Bound = 600; int n, m, q, rt[maxn], a[maxn]; bool isHeavy[maxn]; vector <int> adj[maxn], toAdd; vector <pair <int, int>> toAdd_pairs; set <int> heavy[maxn]; set <pair <int, int>> light[maxn]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int get(const int &x) {return x == rt[x] ? x : rt[x] = get(rt[x]);} void merge(int x, int y){ if((x = get(x)) == (y = get(y))) return; if(N(adj[x]) < N(adj[y])) swap(adj[x], adj[y]); if(N(heavy[x]) < N(heavy[y])) swap(heavy[x], heavy[y]); if(N(light[x]) < N(light[y])) swap(light[x], light[y]); for(int u: adj[y]){ u = get(u); if(isHeavy[u]){ if(isHeavy[x]) heavy[x].insert(u), heavy[u].insert(x); else light[u].insert({a[x], x}); } else if(isHeavy[x]) light[x].insert({a[u], u}); adj[x].push_back(u); } for(int u: heavy[y]) heavy[x].insert(get(u)); for(pair <int, int> t: light[y]) light[x].insert(t); rt[y] = x; if(!isHeavy[x] && N(adj[x]) >= Bound){ isHeavy[x] = true; for(int u: adj[x]){ if((u = get(u)) == x) continue; light[x].insert({a[u], u}); if(isHeavy[u]) heavy[x].insert(u), heavy[u].insert(x); } } } int main(){ cin.tie(0); ios :: sync_with_stdio(0); cin >> n >> m; FO(i, 0, n - 1) FO(j, 0, m - 1) cin >> a[ord(i, j)]; FO(i, 0, n - 1) FO(j, 0, m - 1){ rt[ord(i, j)] = ord(i, j); FO(k, 0, 3){ int x = i + dx[k], y = j + dy[k]; if(x < 0 || y < 0 || x >= n || y >= m) continue; adj[ord(i, j)].push_back(ord(x, y)); if(a[ord(i, j)] == a[ord(x, y)]) toAdd_pairs.push_back({ord(i, j), ord(x, y)}); } } for(pair <int, int> &e: toAdd_pairs) merge(e.first, e.second); cin >> q; while(q--){ int x, y, c; cin >> x >> y >> c; --x, --y; int root = get(ord(x, y)); swap(a[root], c); toAdd.clear(); if(isHeavy[root]){ for(int u: heavy[root]){ u = get(u); if(u != root && a[u] == a[root]) toAdd.push_back(u); } set <pair <int, int>> :: iterator it; while(true){ it = light[root].lower_bound(make_pair(a[root], 0)); if(it == light[root].end() || get(it -> first) != a[root]) break; int u = get(it -> second); if(a[u] == a[root]) toAdd.push_back(u); light[root].erase(it); } } else{ for(int u: adj[root]){ u = get(u); if(u != root && a[u] == a[root]) toAdd.push_back(u); if(isHeavy[u]) light[u].insert({a[root], u}); } } for(int &u: toAdd) merge(root, u); } FO(i, 0, n - 1){ FO(j, 0, m - 1) cout << a[get(ord(i, 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...