Submission #576335

#	Time	Username	Problem	Language	Result	Execution time	Memory
576335		czhang2718	Paint (COI20_paint)	C++17	0 / 100	3050 ms	90996 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;

unordered_map<ll, vi> adj;
map<ll, bool> edge;
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]++;
	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();
			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] << " ";
		}
		// 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; 
			}
		}
	}
	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[h2(u, col[find(v)])].pb(v);
		adj[h2(v, col[find(u)])].pb(u);
		edge[h2(u,v)]=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=par2[h(x,y)];
		col[find(u)]=c;

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

		buffer.pb(u);
		
		for(int v:adj[h2(u,c)]){
			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