Submission #942228

#	Time	Username	Problem	Language	Result	Execution time	Memory
942228		elotelo966	Paint (COI20_paint)	C++17	8 / 100	3064 ms	524288 KiB

paint

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY 100000000000005
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 200005
#define fi first
#define se second

int r,s;
int dizi[lim],vis[lim];// x-y
int old_par[lim];// x-y
int color[4*lim];
int xd[4]={0,0,-1,1},yd[4]={1,-1,0,0};
int par[lim],siz[lim];

set<int> st[lim];
set<int> ekle;

int index(int x,int y){
	return (x-1)*s+y;
}

inline bool cont(int x,int y){
	if(x<1 || y<1 || x>r || y>s)return 0;
	return 1;
}

inline void dfs(int x,int y,int renk,int now){
	if(!cont(x,y))return;
	if(dizi[index(x,y)]!=now)return ;
	if(vis[index(x,y)])return ;
	vis[index(x,y)]=1;
	old_par[index(x,y)]=renk;
	for(int i=0;i<4;i++){
		dfs(x+xd[i],y+yd[i],renk,now);
	}
}

inline void dfs2(int x,int y){
	if(!cont(x,y))return;
	if(vis[index(x,y)])return ;
	vis[index(x,y)]=1;
	for(int i=0;i<4;i++){
		int nx=x+xd[i];
		int ny=y+yd[i];
		if(cont(nx,ny) && dizi[index(x,y)]!=dizi[index(nx,ny)]){
			st[old_par[index(nx,ny)]].insert(old_par[index(x,y)]);
			st[old_par[index(x,y)]].insert(old_par[index(nx,ny)]);
		}
		dfs2(nx,ny);
	}
}

inline int find(int node){
	if(par[node]==node)return node;
	return par[node]=find(par[node]);
}

inline void unite(int node1,int node2){
	//if(siz[node1]<siz[node2])swap(node1,node2);
	//cout<<node1<<" "<<node2<<endl;
	par[node2]=par[node1];
	siz[node1]+=siz[node2];
	for(auto x:st[node2]){
		if(find(x)!=node1)ekle.insert(x);
	}
	//st[node1].erase(node2);
	/*cout<<endl;
	for(auto x:st[node1])cout<<x<<" ";
	cout<<"b"<<endl;*/
}

int32_t main(){
	//faster
	cin>>r>>s;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			cin>>dizi[index(i,j)];
		}
	}
	int cur=1;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			if(vis[index(i,j)]==0){
				dfs(i,j,cur,dizi[index(i,j)]);
				color[cur]=dizi[index(i,j)];
				cur++; // node olarak tanımlama
			}
		}
	}
	memset(vis,0,sizeof(vis));
	/*cout<<endl;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			cout<<old_par[i][j]<<" ";
		}
		cout<<endl;
	}
	*/
	dfs2(1,1);
	/*
	for(int i=1;i<cur;i++){
		cout<<i<<" "<<st[i].size()<<endl;
		for(auto x:st[i])cout<<x<<" ";
		cout<<endl<<endl;
	}
	*/
	////////////////////////////////////////////////////////////////////
	
	for(int i=1;i<cur;i++){
		siz[i]=1;
		par[i]=i;
	}
	
	int q;cin>>q;
	while(q--){
		int a,b,val;cin>>a>>b>>val;
		int nod=find(old_par[index(a,b)]);
		//cout<<nod<<endl;
		for(auto komsu:st[nod]){
			//cout<<find(komsu)<<" "<<komsu<<" "<<color[find(komsu)]<<endl;
			if(find(komsu)==nod)continue;
			if(color[find(komsu)]==val){
				unite(nod,find(komsu));
			}
		}
		for(auto x:ekle)st[nod].insert(x);
		ekle.clear();
		color[nod]=val;
	}
	/*
	for(int i=1;i<cur;i++){
		cout<<par[i]<<" ";
	}*/
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			cout<<color[find(old_par[index(i,j)])]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52