oj.uz

Submission #942228

# Submission time Handle Problem Language Result Execution time Memory
942228 2024-03-10T11:24:13 Z elotelo966 Paint (COI20_paint) C++17
8 / 100
 3000 ms 524288 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17496 KB Output is correct
2 Correct 5 ms 17520 KB Output is correct
3 Correct 13 ms 19800 KB Output is correct
4 Correct 14 ms 19544 KB Output is correct
5 Correct 371 ms 107656 KB Output is correct
6 Correct 48 ms 20060 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 26192 KB Output is correct
2 Correct 113 ms 33372 KB Output is correct
3 Execution timed out 3064 ms 42508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 77740 KB Output is correct
2 Correct 405 ms 76320 KB Output is correct
3 Correct 368 ms 77908 KB Output is correct
4 Correct 1210 ms 77672 KB Output is correct
5 Execution timed out 3029 ms 70044 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 57684 KB Output is correct
2 Execution timed out 3007 ms 524288 KB Time limit exceeded
3 Halted 0 ms 0 KB -