oj.uz

Submission #1003984

# Submission time Handle Problem Language Result Execution time Memory
1003984 2024-06-20T21:14:09 Z vjudge1 Paint (COI20_paint) C++17
8 / 100
 3000 ms 12132 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

int n, m;
vector<vector<int>> grid;
int d[4]={0, 0, -1, 1};

void dfs(int x, int y, int c, int nova){
	grid[x][y]=nova;
	
	for(int i=0;i<4;i++){
		int dx=x+d[i], dy=y+d[3-i];
		if(dx<0 || dx>=n || dy<0 || dy>=m || grid[dx][dy]!=c) continue;
		dfs(dx, dy, c, nova);
	}
}

int pai[MAXN], peso[MAXN], nx[MAXN], ant[MAXN], val[MAXN];

int find(int x){ return (pai[x]==x ? x : pai[x]=find(pai[x])); }
void join(int a, int b){
	a=find(a); b=find(b);
	if(a==b) return;
	
	if(peso[a]>peso[b]) swap(a, b);
	
	pai[a]=b;
	peso[b]=max(peso[b], peso[a]+1);
	nx[b]=max(nx[b], nx[a]);
	ant[b]=min(ant[b], ant[a]);
}

void solve(){
	cin >> n >> m;
	
	grid.resize(n, vector<int>(m));
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin >> grid[i][j];
	
	if(n!=1){
		int q; cin >> q;
		while(q--){
			int x, y, c; cin >> x >> y >> c; x--; y--;
			if(c==grid[x][y]) continue;
			dfs(x, y, grid[x][y], c);
		}
		
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				cout << grid[i][j] << " \n"[j==m-1];
	}
	else{
		swap(n, m);
		
		for(int i=0;i<n;i++) pai[i]=i, nx[i]=i+1, ant[i]=i-1, val[i]=grid[0][i];
		
		for(int i=0;i<n-1;i++)
			if(val[i]==val[i+1]) join(i, i+1);
		
		int q; cin >> q;
		while(q--){
			int x, y, c; cin >> x >> y >> c;
			swap(x, y); x--;
			x=find(x);
			val[x]=c;
			
			int curr=nx[x];
			while(curr!=n && val[curr]==c){
				join(x, curr);
				x=find(x);
				curr=nx[x];
			}
			curr=ant[x];
			while(curr!=-1 && val[curr]==c){
				join(x, curr);
				x=find(x);
				curr=ant[x];
			}
			
			val[x]=c;
		}
		
		for(int i=0;i<n;i++) cout << val[find(i)] << " \n"[i==n-1];
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.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 1 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 166 ms 852 KB Output is correct
6 Correct 229 ms 1160 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 11660 KB Output is correct
2 Correct 182 ms 9396 KB Output is correct
3 Correct 254 ms 11856 KB Output is correct
4 Execution timed out 3007 ms 12132 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3920 KB Output is correct
2 Execution timed out 3030 ms 5200 KB Time limit exceeded
3 Halted 0 ms 0 KB -