Submission #576317

#	Time	Username	Problem	Language	Result	Execution time	Memory
576317		czhang2718	Paint (COI20_paint)	C++17	0 / 100	3085 ms	118292 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 rep(i,a,b) for(int i=a; i<=b; i++)

const int N=300001;
int r, c, q;

vi adj[N];

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

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

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;
	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))];
			// 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; 
			}
		}
	}
	for(auto edge:mp){
		int hash=edge.f;
		int u=hash/N;
		int v=hash%N;
		// cout << "adj " << u << " " << v << nl;
		adj[u].pb(v);
		adj[v].pb(u);
	}
}

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--){
		int x, y, c; 
		cin >> x >> y >> c;
		int u=find(h(x,y));
		col[u]=c;
		for(int v:adj[u]){
			// cout << u << "->" << v << nl;
			if(col[find(v)]==c) join(u,v);
		}
		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)

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