Submission #576522

#TimeUsernameProblemLanguageResultExecution timeMemory
576522balbitPaint (COI20_paint)C++14
100 / 100
647 ms28248 KiB
#include <bits/stdc++.h> //#define int ll using namespace std; #define ll long long #define y1 zck_is_king #define pii pair<ll, ll> #define ull unsigned ll #define f first #define s second #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define SQ(x) (x)*(x) #define MN(a,b) a = min(a,(__typeof__(a))(b)) #define MX(a,b) a = max(a,(__typeof__(a))(b)) #define pb push_back #define REP(i,n) for (int i = 0; i<n; ++i) #define RREP(i,n) for (int i = n-1; i>=0; --i) #define REP1(i,n) for (int i = 1; i<=n; ++i) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #ifdef BALBIT #define IOS() #define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__); template<typename T> void _do(T &&x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);} #else #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' #define bug(...) #endif const int iinf = 1e9+10; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9+7 ; void GG(){cout<<"0\n"; exit(0);} ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod ll re=1; while (n>0){ if (n&1) re = re*a %mo; a = a*a %mo; n>>=1; } return re; } ll inv (ll b, ll mo = mod){ if (b==1) return b; return (mo-mo/b) * inv(mo%b,mo) % mo; } const int maxn = 2e5+5; const int BS = 300; int color[maxn], sz[maxn],par[maxn]; map<int, set<int> > touch[maxn/BS+3]; int touchpos[maxn]; int TID = 0; vector<int> here[maxn]; bool adj[maxn/BS+3][maxn/BS+3]; int whose[maxn/BS+3]; int n,m; inline int getid(int i, int j) { return i*m+j; } int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); } int dx[] = {0,-1,0,1}; int dy[] = {1,0,-1,0}; inline bool ingrid(int r, int c) { return r>=0&&r<n&&c>=0&&c<m; } bool tmpseen[maxn]; vector<int> getadj(int x) { vector<int> re; for (int e : here[x]) { int er = e/m, ec = e%m; REP(k,4) { int tr = er + dx[k], tc = ec + dy[k]; if (ingrid(tr, tc)) { int hi = find(getid(tr,tc)); if (!tmpseen[hi]) { re.pb(hi); tmpseen[hi] = 1; } } } } for (int y : re) tmpseen[y] = 0; return re; } void mrg(int a, int b) { a = find(a); b = find(b); if (a == b) { return; } assert(color[a] == color[b]); if (SZ(here[a]) < SZ(here[b])) swap(a,b); // merge b into a bool yoink = 0; if (SZ(here[a]) >= BS) { int tpa = touchpos[a]; if (SZ(here[b]) >= BS) { int tpb = touchpos[b]; // big - big for (auto &e : touch[tpb]) { for (int r : e.s) touch[tpa][e.f].insert(r); } map<int, set<int> > () . swap(touch[tpb]); REP(k, TID) { if (adj[tpb][k]) adj[tpa][k] = adj[k][tpa] = 1; } // REP(r, 100002) { // touch[tpa][r].insert(touch[tpa][r].end(), ALL(touch[tpb][r])); // vector<int>().swap(touch[tpa][r]); // } }else{ for (int hi : getadj(b)) { if (color[hi] != color[a]) { if (touchpos[hi] != -1) { adj[tpa][touchpos[hi]] = adj[touchpos[hi]][tpa] = 1; }else{ touch[tpa][color[hi]].insert(hi); } }else { // assert(hi == a || hi == b); } } } }else{ yoink = 1; } here[a].insert(here[a].end(), ALL(here[b])); par[b] = a; if (yoink && SZ(here[a]) >= BS) { // upgrade it whose[TID] = a; int tpa = touchpos[a] = TID++; for (int e : getadj(a)) { if (color[e] != color[a]) { if (touchpos[e] != -1) { adj[tpa][touchpos[e]] = adj[touchpos[e]][tpa] = 1; }else{ touch[tpa][color[e]].insert(e); } }else{ // assert(e == a); } } } } void go(int id, int col) { id = find(id); int r = id/m, c = id%m; color[id] = col; vector<int> tomerge; if (SZ(here[id]) >= BS) { // yarrr i'm biggg int tp = touchpos[id]; vector<int> todo; if (touch[tp].count(col)) for (int hm : touch[tp][col]) { int hh = find(hm); if (hh != id && color[hh] == col) { if (!tmpseen[hh]) tomerge.pb(hh), tmpseen[hh] = 1; } } touch[tp][col].clear(); set<int>().swap(touch[tp][col]); touch[tp].erase(col); REP(j, TID) { int who = whose[j]; if (tp!=j && (adj[j][tp]||adj[tp][j]) && par[who] == who && color[who] == col) { if (!tmpseen[who]) tomerge.pb(who), tmpseen[who] = 1; } } }else{ // smol boi for (int hi : getadj(id)) { if (hi != id && color[hi] == col) { tomerge.pb(hi); } } } for (int t : tomerge) { mrg(id, t); tmpseen[t] = 0; } id = find(id); if (SZ(here[id]) < BS) { for (int hi : getadj(id)) { if (hi != id && color[hi] != col && touchpos[hi] != -1) { touch[touchpos[hi]][col].insert(id); } } } } signed main(){ IOS(); memset(touchpos, -1, sizeof touchpos); cin>>n>>m; vector<vector<int> > g; g.resize(n, vector<int> (m,0)); REP(i,n) REP(j,m) { cin>>g[i][j]; g[i][j]; here[getid(i,j)].pb(getid(i,j)); color[getid(i,j)] = g[i][j]; par[getid(i,j)] = getid(i,j); } REP(i,n) REP(j,m) { REP(t,4) { int I = i + dx[t], J = j + dy[t]; if (ingrid(I,J) && color[getid(i,j)] == color[getid(I,J)]) { mrg(getid(i,j), getid(I,J)); } } } int qu; cin>>qu; REP(ar, qu) { int r,c; cin>>r>>c; --r; --c; int ncol; cin>>ncol; go(getid(r,c), ncol); } REP(i,n) REP(j,m) { int it = getid(i,j); bug(it, find(it)); if (find(it) == it) { for (int e : here[it]) { bug(e/m, e%m, color[it]); g[e/m][e%m] = color[it]; } } } REP(i,n) REP(j,m) { cout<<g[i][j]<<" \n"[j==m-1]; } }

Compilation message (stderr)

paint.cpp: In function 'void go(int, int)':
paint.cpp:172:9: warning: unused variable 'r' [-Wunused-variable]
  172 |     int r = id/m, c = id%m;
      |         ^
paint.cpp:172:19: warning: unused variable 'c' [-Wunused-variable]
  172 |     int r = id/m, c = id%m;
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...