oj.uz

Submission #775666

# Submission time Handle Problem Language Result Execution time Memory
775666 2023-07-06T18:05:50 Z DangerNoodle7591 Paint (COI20_paint) C++17
9 / 100
 43 ms 7384 KB 
#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
//#define int long long int
#define N 200005
int limit[N][2],renk[N];
int father[N];
int dsu(int x){
	if(father[x]==x)return x;
	return father[x]=dsu(father[x]);
}
void kardes(int x,int y){
	x=dsu(x),y=dsu(y);
	if(x==y)return;
	father[y]=x;
	limit[x][0]=min(limit[x][0],limit[y][0]);

	limit[x][1]=max(limit[x][1],limit[y][1]);
}
int geldik[N];
int main(){
	lalala;
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			cin>>renk[j];
			limit[j][0]=limit[j][1]=j;
			father[j]=j;
		}
	}
	for(int i=1;i<=m;i++){
		if(geldik[i])continue;
		geldik[i]=1;
		for(int j=i-1;j>0;j--){
			if(renk[j]!=renk[i])break;

			geldik[j]=1;
			kardes(i,j);
		}
		for(int j=i+1;j<=m;j++){
			if(renk[j]!=renk[i])break;
			geldik[j]=1;
			kardes(i,j);
		}
	}
	int q;cin>>q;
	while(q--){
		int x_x,uwu,OwO;cin>>x_x>>uwu>>OwO;
		uwu=dsu(uwu);
		int alt=limit[uwu][0]-1, ust=limit[uwu][1]+1;
		renk[uwu]=OwO;
		if(alt>0&&renk[dsu(alt)]==OwO){
			kardes(uwu,dsu(alt));
		}
		if(ust<=m&&renk[dsu(ust)]==OwO){
			kardes(uwu,dsu(ust));
		}
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			cout<<renk[dsu(j)]<<" ";
		}cout<<endl;
	}

	
	
}

Subtask #1
0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2460 KB Output is correct
2 Correct 27 ms 3648 KB Output is correct
3 Correct 43 ms 7384 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 52.0

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