oj.uz

Submission #966448

# Submission time Handle Problem Language Result Execution time Memory
966448 2024-04-19T22:14:35 Z jcelin Paint (COI20_paint) C++14
100 / 100
 624 ms 456020 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14684 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 8 ms 15596 KB Output is correct
4 Correct 12 ms 20148 KB Output is correct
5 Correct 12 ms 20572 KB Output is correct
6 Correct 22 ms 25148 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 19560 KB Output is correct
2 Correct 192 ms 216792 KB Output is correct
3 Correct 92 ms 39184 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 51292 KB Output is correct
2 Correct 156 ms 56516 KB Output is correct
3 Correct 163 ms 73728 KB Output is correct
4 Correct 201 ms 130600 KB Output is correct
5 Correct 171 ms 161760 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 42068 KB Output is correct
2 Correct 249 ms 49124 KB Output is correct
3 Correct 473 ms 222440 KB Output is correct
4 Correct 624 ms 456020 KB Output is correct
5 Correct 279 ms 126180 KB Output is correct
6 Correct 321 ms 160848 KB Output is correct
7 Correct 242 ms 123832 KB Output is correct
8 Correct 179 ms 95908 KB Output is correct
9 Correct 235 ms 45376 KB Output is correct