Submission #577434

#	Time	Username	Problem	Language	Result	Execution time	Memory
577434		czhang2718	Paint (COI20_paint)	C++17	0 / 100	127 ms	25404 KiB

paint

#include "bits/stdc++.h"
using namespace std;
 
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second
#define pb push_back
#define nl '\n'
#define sz(x) (int) x.size()
#define rep(i,a,b) for(int i=a; i<=b; i++)
 
const int N=200000;
const int B=400;
int r, c, q;
 
vector<vi> g;
 
int par[N];
int sz[N];
int col[N];
vi adj[N];
vi big;
map<int, set<int>> adj2[N];
 
int dx[]={-1, 0, 0, 1};
int dy[]={0, -1, 1, 0};
 
 
int find(int x){
	return par[x]==x?x:par[x]=find(par[x]);
}
 
void join(int x, int y){
	// cout << "join " << x << " " << y << nl;
	int a=find(x);
	int b=find(y);
	if(a==b) return;
	// cout << "ab " << a <<  " " << b << nl;
	if(sz[b]>sz[a]) swap(a,b);
 
	if(sz[a]>B && sz[b]>B){
		for(auto e:adj2[b]){
			for(int k:e.s) adj2[a][e.f].insert(k); // shouldn't need find(k)
		}
	}
 
	else if(sz[a]>B && sz[b]<=B){
		for(int k:adj[b]){
			int c=col[find(k)];
			if(k!=a && k!=b) adj2[a][c].insert(find(k));
		}
	}
 
	else if(sz[a]+sz[b]<=B) {
		for(int k:adj[b]) if(find(k)!=a && find(k)!=b) adj[a].pb(k);
	}
 
	if(sz[a]+sz[b]>B && sz[a]<=B){
		big.pb(a);
		for(int k:adj[a]) if(find(k)!=a && find(k)!=b) adj2[a][col[find(k)]].insert(find(k));
	}
	
	par[b]=a;
	sz[a]+=sz[b];
}
 
int h(int i, int j){
	return c*i+j;
}
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
 
	cin >> r >> c;
	g.resize(r, vi(c));
 
	rep(i,0,r-1){
		rep(j,0,c-1){
			par[h(i,j)]=h(i,j);
          	sz[h(i,j)]=1;
			rep(k,0,1){
				int x=i+dx[k];
				int y=j+dy[k];
				if(x<0 || y<0) continue;
				adj[h(i,j)].pb(h(x,y));
				adj[h(x,y)].pb(h(i,j));
			}
		}
	}
 
	rep(i,0,r-1){
		rep(j,0,c-1){
			cin >> g[i][j];
			col[h(i,j)]=g[i][j];
			rep(k,0,1){
				int x=i+dx[k];
				int y=j+dy[k];
				if(x<0 || y<0) continue;
				// cout << g[i][j] << "=" << g[x][y] << nl;
				if(g[i][j]==g[x][y]) join(h(i,j), h(x,y)); 
			}
		}
	}
 
 
	cin >> q;
	while(q--){
		// cout << "Q " <<q << nl;
		int x, y, c;
		cin >> x >> y >> c;
		x--; y--;
 
		int i=find(h(x,y));
		col[i]=c;
 
		if(sz[i]>B){
			vi nei;
			for(int p:adj2[i][c]) nei.pb(p);
			adj2[i][c].clear();
			for(int k:nei) if(col[find(k)]==c) join(i, k);
		}
		else{
			vi nei;
			for(int p:adj[i]) nei.pb(p);
			for(int k:nei){
				if(col[find(k)]==c) join(i, k);
			}
		}
 
		i=find(i);
 
		if(sz[i]<=B){
			for(int k:adj[i]){
				if(sz[find(k)]>B && find(k)!=i) adj2[find(k)][c].insert(i);
			}
		}
		else{
			for(int j:big){
				j=find(j);
				if(j==i) continue;
				if(adj2[i][col[j]].find(j)!=adj2[i][col[j]].end()) adj2[j][c].insert(i);
			}
		}
	}
 
	
 
	rep(i,0,r-1){
		rep(j,0,c-1){
			cout << col[find(h(i,j))] << " ";
		}
		cout << nl;
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52