Submission #1003984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003984		vjudge1	Paint (COI20_paint)	C++17	8 / 100	3030 ms	12132 KiB

paint

#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 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52