Submission #773787

#	Time	Username	Problem	Language	Result	Execution time	Memory
773787		vjudge1	Paint (COI20_paint)	C++17	0 / 100	77 ms	30324 KiB

paint

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define endl "\n"
#define ll long long
#define N 200005
#define pb push_back
vector<int> adj[N];
int father[N], siz[N];
int dsu(int x){
	if(father[x]==x)return x;
	return father[x]=dsu(father[x]);
}
int kardes(int x,int y,int yes){
	int fax=dsu(x),fay=dsu(y);
	if(fay==fax)return 1;
	if(siz[fax]<siz[fay])swap(fax,fay);
	if(yes){
		for(auto u:adj[fay]){
			if(u!=fax)adj[fax].pb(u);
		}
	}
	siz[fax]+=siz[fay];
	father[fay]=fax;
	return 0;
}

int var[N],arr[N],renk[N],gel[N];
int n,m;
void bfs(int x,int co){
	queue<int> q;
	q.push(x);
	while(q.size()){
		int a=q.front();q.pop();
		if(var[a])continue;
		var[a]=1;
		if((a-1)%m&&var[a-1]==0&&renk[a-1]==co){q.push(a-1);kardes(x,a-1,0);}
		
		if(a%m&&var[a+1]==0&&renk[a+1]==co){q.push(a+1);kardes(x,a+1,0);}
		
		if(a-m>0&&var[a-m]==0&&renk[a-m]==co){q.push(a-m);kardes(x,a-m,0);}

		if(a+m<=n*m&&var[a+m]==0&&renk[a+m]==co){q.push(a+m);kardes(x,a+m,0);}
	}
}
void beef(int x,int co){
	queue<int> q;
	q.push(x);
	map<int,int>mp;
	while(q.size()){
		int a=q.front();q.pop();
		if(gel[a])continue;
		gel[a]=1;
		if((a-1)%m&&gel[a-1]==0){
			if(renk[dsu(a-1)]!=co&&mp[dsu(a-1)]==0){
				adj[dsu(a)].pb(dsu(a-1));mp[dsu(a-1)]=1;
				adj[dsu(a-1)].pb(dsu(a));
			}
			else if(renk[a-1]==co)q.push(a-1);
		}
		if(a%m&&gel[a+1]==0){
			if(renk[dsu(a+1)]!=co&&mp[dsu(a+1)]==0){
				adj[dsu(a)].pb(dsu(a+1));mp[dsu(a+1)]=1;
				adj[dsu(a+1)].pb(dsu(a));
			}
			else if(renk[a+1]==co) q.push(a+1);
		}
		if(a-m>0&&gel[a-m]==0){
			if(renk[dsu(a-m)]!=co&&mp[dsu(a-m)]==0){
				adj[dsu(a)].pb(dsu(a-m));mp[dsu(a-m)]=1;
				adj[dsu(a-m)].pb(dsu(a));
			}
			else if(renk[a-m]==co)q.push(a-m);
		}
		if(a+m<=n*m&&gel[a+m]==0){
			if(renk[dsu(a+m)]!=co&&mp[dsu(a+m)]==0){
				adj[dsu(a)].pb(dsu(a+m));mp[dsu(a+m)]=1;
				adj[dsu(a+m)].pb(dsu(a));
			}
			else if(renk[a+m]==co) q.push(a+m);
		}
	}
}
int main(){
	lalala;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=(i-1)*m+j;
			cin>>renk[x];
			father[x]=x;
			siz[x]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=(i-1)*m+j;
			if(var[x])continue;
			bfs(x,renk[x]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=(i-1)*m+j;
			if(gel[x])continue;
			beef(x,renk[x]);
		}
	}
	int q;cin>>q;
	while(q--){
		int x,yyy,mor;cin>>x>>yyy>>mor;
		x=(x-1)*m+yyy;
		x=dsu(x);
		if(renk[x]==mor)continue;
		renk[x]=mor;
		for(auto u:adj[x]){
			if(renk[u]==mor){
				kardes(x,u,1);
			}
		}

	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=(i-1)*m+j;
			cout<<renk[dsu(x)];
		}cout<<endl;
	}
	
}

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