Submission #576346

#	Time	Username	Problem	Language	Result	Execution time	Memory
576346		czhang2718	Paint (COI20_paint)	C++17	0 / 100	3043 ms	109996 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=200020;
const int B=500;
int r, c, q;

vi buffer;

// vi adj[N];

int dx[]={-1, 0, 0, 1};
int dy[]={0, -1, 1, 0};

// dsu
int par[N], par2[N];
int rnk[N];
int col[N];
vector<vi> g;
int deg[N];

map<int, vi> adj[N];
map<int, bool> edge[N];
bool touch[N];

int find(int x){
	return par[x]==x?x:par[x]=find(par[x]);
}

bool join(int x, int y){
	int a=find(x);
	int co=col[a];
	int b=find(y);
	col[a]=col[b]=co;
	if(a==b) return 0;
	// cout << "join " << a/(c+1) << " " << a%(c+1) << " w " << b/(c+1) << " " << b%(c+1) << nl;
	// if(rnk[a]!=rnk[b] && rnk[a]<rnk[b]) par[a]=b;
	// else par[b]=a;
	// if(rnk[a]==rnk[b]) rnk[a]++;

	if(deg[a]>deg[b]) swap(a,b);
	adj[b].insert(adj[a].begin(), adj[a].end());
	edge[b].insert(edge[a].begin(), edge[a].end());

	par[a]=b;
	deg[b]+=deg[a];

	return 1;
}

int h(int i, int j){
	return (c+1)*i+j;
}

ll h2(int i,int j){
	if(i>j) swap(i,j);
	return ll(N)*i+j;
}

void create(){
	unordered_map<ll, bool> mp;
	// edge.clear();
	// edge.reserve(N);
	mp.reserve(4*r*c);
	rep(i,1,r){
		rep(j,1,c){
			adj[h(i,j)].clear();
			edge[h(i,j)].clear();
			g[i][j]=col[find(h(i,j))];
			par2[h(i,j)]=find(h(i,j));
			// touch[h(i,j)]=0;
			// cout << g[i][j] << " ";
			deg[h(i,j)]=0;
		}
		// cout << nl;
	}
	// cout << nl;
	rep(i,1,r){
		rep(j,1,c){
			rep(k,0,1){
				int x=i+dx[k];
				int y=j+dy[k];
				if(!x || !y || x>r || y>c) continue;
				if(g[i][j]!=g[x][y]) mp[{h2(find(h(i,j)), find(h(x,y)))}]=1; 
				// else assert(find(h(i,j))==find(h(x,y)));
				// else{
				// 	if(find(h(i,j))!=find(h(x,y))){
				// 		cout << i << j << " " << x << y << nl;
				// 		cout << "BAD\n";
				// 		exit(0);
				// 	}
				// }
			}
		}
	}
	// adj.clear();
	// adj.reserve(sz(mp)*2);
	for(auto e:mp){
		ll hash=e.f;
		int u=hash/N;
		int v=hash%N;
		// cout << "adj " << u << " " << v << nl;
		adj[u][col[find(v)]].pb(v);
		adj[v][col[find(u)]].pb(u);
		deg[u]++;
		deg[v]++;
		edge[u][v]=edge[v][u]=1;
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> r >> c;
	g.resize(r+1, vi(c+1));

	rep(i,1,r){
		rep(j,1,c){
			cin >> g[i][j];
			par[h(i,j)]=h(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 || !y) continue;
				if(g[i][j]==g[x][y]) join(h(i,j), h(x,y)); 
			}
		}
	}

	create();

	cin >> q;
	while(q--){
		// cout << "Q " << q << nl;
		int x, y, c; 
		cin >> x >> y >> c;
		int u=find(h(x,y));
		col[u]=c;

		for(int i:buffer){
			int co=col[find(i)];
			if(co!=c) continue;
			if(edge[u].find(i)!=edge[u].end()) join(u,i);
		}

		buffer.pb(u);
		
		for(int v:adj[u][c]){
			if(find(v)==find(u)) continue;
			int real_c=col[find(v)];
			if(real_c!=c) continue;
			buffer.pb(v);
			join(u,v);
		}


		if(sz(buffer)>B){
			create();
			buffer.clear();
		}
	}

	create();


	rep(i,1,r){
		rep(j,1,c){
			cout << g[i][j] << " ";
		}
		cout << nl;
	}
}
// graph
// color node, merge neighbors with same color
// sqrt batch: no. merged nodes >= B -> recreate graph
// adj sets
// query: unordered map {u, {col=k}} 
// 		  + check newly changed nodes
// what if you change x, x, x, x
// dsu, par, col


// slow:
// iterate same adj, merge, call this set X
// keep list of neighbors of adj
// erase orig edges v->X
// for v:list, add v->root(X)


// optimize: touch[u]

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