Submission #577429

#	Time	Username	Problem	Language	Result	Execution time	Memory
577429		czhang2718	Paint (COI20_paint)	C++17	0 / 100	446 ms	47624 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=500;
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]){
			k=find(k);
			int c=col[k];
			if(k!=a && k!=b) adj2[a][c].insert(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;
				if(g[i][j]==g[x][y]) join(h(i,j), h(x,y)); 
			}
		}
	}


	cin >> q;
	while(q--){
		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){
			// assert(adj[i].size()<=4*sz[i]);
			for(int k:adj[i]){
				k=find(k);
				if(sz[k]>B && k!=i) adj2[k][c].insert(i);
			}
		}
		else{
			// assert(big.size()<=r*c/B);
			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