Submission #539449

#TimeUsernameProblemLanguageResultExecution timeMemory
539449hhhhauraPaint (COI20_paint)C++14
48 / 100
3079 ms23696 KiB
#define wiwihorz #include <bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i ++) #define rrep(i, a, b) for(int i = b; i >= a; i--) #define ceil(a, b) ((a + b - 1) / (b)) #define all(x) x.begin(), x.end() #define int long long int #define lld long double #define pii pair<int, int> #define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()) #define INF 1000000000000000000 #define MOD 1000000007 #define eps (1e-9) using namespace std; #ifdef wiwihorz #define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a) void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L)==R], ++L;} void kout(){cerr<< endl;} template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);} #else #define print(...) 0 #define vprint(...) 0 #endif #define x first #define y second namespace solver { int r, c, n, m; vector<vector<int>> mp, ch; vector<int> par, rk, col; vector<int> dirx = {0, 0, 1, -1}; vector<int> diry = {1, -1, 0, 0}; void init_(int _r, int _c) { r = _r, c = _c; n = r * c; par.assign(n, 0); iota(all(par), 0); rk.assign(n, 0); col.assign(n, 0); ch.assign(n, vector<int>()); mp.assign(r, vector<int>(c, 0)); rep(i, 0, r - 1) rep(j, 0, c - 1) { int cur = i * c + j; rep(k, 0, 3) { int nx = i + dirx[k]; int ny = j + diry[k]; if(nx < 0 || nx >= r) continue; if(ny < 0 || ny >= c) continue; ch[cur].push_back(nx * c + ny); } } } int find_par(int x) { if(par[par[x]] == par[x]) return par[x]; else return par[x] = find_par(par[x]); } void unite(int a, int b) { int aa = find_par(a); int bb = find_par(b); if(aa == bb) return; vector<int> v; for(auto i : ch[aa]) if(find_par(i) != bb) v.push_back(i); for(auto i : ch[bb]) if(find_par(i) != aa) v.push_back(i); ch[aa].clear(), ch[bb].clear(); if(rk[aa] > rk[bb]) par[bb] = aa, ch[aa] = v; else if(rk[bb] > rk[aa]) par[aa] = bb, ch[bb] = v; else rk[aa]++, par[bb] = aa, ch[aa] = v; } void solve() { rep(i, 0, r - 1) rep(j, 0, c - 1) col[i * c + j] = mp[i][j]; rep(i, 0, r - 1) rep(j, 0, c - 1) { int cur = i * c + j; rep(k, 0, 3) { int nx = i + dirx[k]; int ny = j + diry[k]; if(nx < 0 || nx >= r) continue; if(ny < 0 || ny >= c) continue; if(mp[i][j] == mp[nx][ny]) unite(cur, nx * c + ny); } } cin >> m; rep(i, 1, m) { int x, y, val; cin >> x >> y >> val; x--, y--; int p = find_par(x * c + y); col[p] = val; vector<int> tp = ch[p]; for(auto j : tp) if(col[find_par(j)] == val) unite(p, j); } rep(i, 0, r - 1) rep(j, 0, c - 1) { cout << col[find_par(i * c + j)] << " \n"[j + 1 == c]; } } }; using namespace solver; signed main() { ios::sync_with_stdio(false), cin.tie(0); int r, c; cin >> r >> c; init_(r, c); rep(i, 0, r - 1) rep(j, 0, c - 1) cin >> mp[i][j]; solve(); return 0; }

Compilation message (stderr)

paint.cpp:17:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L)==R], ++L;}
      |             ^~~~
paint.cpp:17:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L)==R], ++L;}
      |                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...