Submission #966448

#	Time	Username	Problem	Language	Result	Execution time	Memory
966448		jcelin	Paint (COI20_paint)	C++14	100 / 100	624 ms	456020 KiB

paint

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 2e5 + 7;
const int cx = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int block = 600;


int par[MAXN], col[MAXN], n, m;
vi pop[MAXN], adj[MAXN];
vector<set<int>> sus[MAXN];
set<int> vel;
bool bg[MAXN], unutar[MAXN];

void merge(int a, int b){
	if(pop[a].size() < pop[b].size()) swap(a, b);
	
	if(pop[a].size() < block and pop[a].size() + pop[b].size() >= block){
		sus[a].resize(cx);
		vel.insert(a);
		bg[a] = 1;
		for(int x : adj[a]){
			x = par[x];
			sus[a][col[x]].insert(x);
		}
	}
	
	if(pop[a].size() + pop[b].size() >= block){
		for(int x : adj[b]){
			x = par[x];
			if(x != a) sus[a][col[x]].insert(x);
		}
		
		if(bg[b]){				
			sus[b].clear();
			sus[b].shrink_to_fit();
			vel.erase(b);
			bg[b] = 0;	
		}
	}
	
	for(int x : pop[b]) pop[a].PB(x), par[x] = a;
	for(int x : adj[b]) adj[a].PB(x);
	adj[b].clear();
	adj[b].shrink_to_fit();
	pop[b].clear();
	adj[b].shrink_to_fit();
}

void prin(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++) cout << col[par[i * m + j]] << " ";
		cout << "\n";
	}
}

void bojaj(int a, int c){
	a = par[a];
	col[a] = c;
	while(1){
		if(!bg[a]){
			bool naso = 0;
			for(int x : adj[a]){
				x = par[x];
				if(a != x and col[x] == c){
					merge(a, x);
					a = par[a];
					naso = 1;
					break;
				}
			}
			if(!naso) break;
		}else{
			if(sus[a][c].empty()) break;
			int x = *sus[a][c].begin();
			sus[a][c].erase(x);
			x = par[x];
			if(a != x and col[x] == c){
				merge(a, x);
				a = par[a];
			}
		}
	}
	
	
	if(!bg[a]){
		vi novi;
		for(int x : adj[a]){
			x = par[x];
			if(x != a and !unutar[x]){
				unutar[x] = 1;
				novi.PB(x);
			}
		}
		
		adj[a] = novi;
		for(int x : vel) if(unutar[x]) sus[x][c].insert(a);
		for(int x : novi) unutar[x] = 0;
	}else{
		for(int x : vel){
			x = par[x];
			if(a != x and sus[a][col[x]].count(x)) sus[x][c].insert(a);
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int x;
			cin >> x;
			int cr = i * m + j;
			col[cr] = x;
			pop[cr].PB(cr);
			par[cr] = cr;
			for(int k=0; k<4; k++){
				int ni = i + dx[k], nj = j + dy[k];
				if(ni < 0 or ni >= n or nj < 0 or nj >= m) continue;
				int nc = ni * m + nj;
				adj[cr].PB(nc);
			}
		}
	}
	for(int i=0; i<n*m; i++) bojaj(i, col[i]);
	
	int q;
	cin >> q;
	while(q--){
		int r, s, c;
		cin >> r >> s >> c;
		r--, s--;
		bojaj(r * m + s, c);
		//prin();
	}
	
	prin();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

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