oj.uz

Submission #577392

# Submission time Handle Problem Language Result Execution time Memory
577392 2022-06-14T17:19:11 Z czhang2718 Paint (COI20_paint) C++17
8 / 100
 3000 ms 524288 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=200;
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]){
			int c=col[find(k)];
			if(k!=a && k!=b) adj2[a][c].insert(find(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);
			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;
				// cout << g[i][j] << "=" << g[x][y] << nl;
				if(g[i][j]==g[x][y]) join(h(i,j), h(x,y)); 
			}
		}
	}


	cin >> q;
	while(q--){
		// cout << "Q " <<q << nl;
		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){
			for(int k:adj[i]){
				if(sz[find(k)]>B && find(k)!=i) adj2[find(k)][c].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][c].insert(i);
			}
		}
	}

	

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14548 KB Output is correct
3 Correct 16 ms 14932 KB Output is correct
4 Correct 16 ms 15036 KB Output is correct
5 Correct 380 ms 133684 KB Output is correct
6 Correct 487 ms 18644 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17068 KB Output is correct
2 Correct 97 ms 19908 KB Output is correct
3 Execution timed out 3075 ms 25172 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1991 ms 28724 KB Output is correct
2 Correct 765 ms 28304 KB Output is correct
3 Correct 698 ms 28872 KB Output is correct
4 Correct 2966 ms 28208 KB Output is correct
5 Execution timed out 3071 ms 26320 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 25004 KB Output is correct
2 Runtime error 880 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -