oj.uz

Submission #577507

# Submission time Handle Problem Language Result Execution time Memory
577507 2022-06-14T23:22:08 Z czhang2718 Paint (COI20_paint) C++17
31 / 100
 438 ms 47612 KB 
#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]; // vector

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


int find(int x){
	return par[x]==x?x:par[x]=find(par[x]);
}

void join(int x, int y){
	int a=find(x);
	int b=find(y);

	if(a==b) return;

	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){
				if(find(k)!=a && find(k)!=b) adj2[a][col[find(k)]].insert(find(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]<=B) {
		for(int k:adj[b]) if(find(k)!=a && find(k)!=b) adj[a].pb(find(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));
		}
		adj[a].clear();
	}
	
	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, co;
		cin >> x >> y >> co;
		x--; y--;

		int i=find(h(x,y));
		col[i]=co;

		if(sz[i]>B){
			vi nei;
			for(int p:adj2[i][co]) nei.pb(p);
			adj2[i][co].clear();
			for(int k:nei) if(col[find(k)]==co) join(i, k);
		}
		else{
			vi nei;
			for(int p:adj[i]) nei.pb(p);
			for(int k:nei){
				if(col[find(k)]==co) join(i, k);
			}
		}

		i=find(i);

		if(sz[i]<=B){
			for(int k:adj[i]){
				k=find(k);
				if(sz[k]>B) adj2[k][co].insert(i);
			}
		}
		else{
			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][co].insert(i);
					// adj2[j][oldc].erase(old);
				}
			}
		}
	}

	

	rep(i,0,r-1){
		rep(j,0,c-1){
			cout << col[find(h(i,j))] << " ";
		}
		cout << nl;
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 12 ms 14932 KB Output is correct
4 Correct 14 ms 14936 KB Output is correct
5 Incorrect 22 ms 16212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 17012 KB Output is correct
2 Correct 99 ms 19952 KB Output is correct
3 Incorrect 121 ms 30176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 25084 KB Output is correct
2 Correct 114 ms 25412 KB Output is correct
3 Correct 138 ms 25436 KB Output is correct
4 Correct 135 ms 26176 KB Output is correct
5 Correct 137 ms 25140 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 23776 KB Output is correct
2 Incorrect 438 ms 47612 KB Output isn't correct
3 Halted 0 ms 0 KB -