oj.uz

Submission #345661

# Submission time Handle Problem Language Result Execution time Memory
345661 2021-01-07T19:39:49 Z pggp Paint (COI20_paint) C++14
0 / 100
 3000 ms 124116 KB 
#include <bits/stdc++.h>

using namespace std;

int R, S;
int parent[250000];
int siz[250000];

bool db = false;

int find(int x){
	if(parent[x] == x){
		return x;
	}
	return parent[x] = find(parent[x]);
}

void un(int x, int y){
	parent[find(x)] = find(y);
}






vector < int > E[250000];
int col[250000];
bool active[250000];

void union_vertices(vector < int > X, int y){
	if(!active[y])	return;
	vector < int > X1;
	set < int > x1S;
	for(int x : X){
		if(active[x]){
			X1.push_back(x);
			x1S.insert(x);
			un(x, y);
			active[x] = false;
		}	
	}
	//cout << "UNION " << x << " " << y << endl;
	
	set < int > S;
	vector < int > v;
	vector < int > v1;
	for(int ver : E[y]){
		if(x1S.find(ver) == x1S.end() and active[ver]){
			S.insert(ver);
			v.push_back(ver);
		}
	}
	for(int x : X1){
		for(int ver : E[x]){
			if(S.find(ver) == S.end() and active[ver]){
				S.insert(ver);
				v1.push_back(ver);
			}
		}
	}
	E[y].clear();
	for(int ver : v){
		//cout << "ver = " << ver << endl;
		E[y].push_back(ver);
	}
	for(int ver : v1){
		if(ver == y)	continue;
		//cout << "ver = " << ver << endl;
		E[y].push_back(ver);
		E[ver].push_back(y);
	}
}

bool used[250000];
stack < int > us;


void color(int v, int c){
	//cout << v << ":" << c << endl;
	col[v] = c;
	vector < int > t = E[v];
	vector < int > to_activ;
	for(int ver : t){
		if(col[ver] == c){
			to_activ.push_back(ver);
		}
	}
	union_vertices(to_activ, v);
}



void print_output(){
	for (int y = 0; y < R; ++y)
	{
		for (int x = 0; x < S; ++x)
		{
			cout << col[find(y * S + x)] << " ";
			if(db)	cout << "(" << find(y * S + x) << ")";
		}
		cout << endl;
	}
	if(db)
	{
		for(int i = 0; i < R * S; i++){
		cout << i << ": ";
		for(int v : E[i]){
			cout << v << " ";
		}
		cout << endl;
		}
	}
}

void dfs(int v, int c){
	used[v] = true;
	us.push(v);
	int c1 = col[v];
	for(int ver : E[v]){
		if(!used[ver] and col[ver] == col[v]){
			dfs(ver, c);
		}
	}
	col[v] = c;
}

void color2(int v, int c){
	dfs(v, c);
	while(!us.empty()){
		used[us.top()] = false;
		us.pop();
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> R >> S;
	for (int i = 0; i < R * S; ++i)
	{
		active[i] = true;
		col[i] = 100001 + i;
		parent[i] = i;
		if(i % S != S - 1){
			E[i].push_back(i + 1);
		}
		if(i % S != 0){
			E[i].push_back(i - 1);
		}
		if(i >= S){
			E[i].push_back(i - S);
		}
		if(i < R*S - S){
			E[i].push_back(i + S);
		}
	}

		

	if(R * S <= 10000 ){
for (int y = 0; y < R; ++y)
	{
		for (int x = 0; x < S; ++x)
		{
			int c;
			cin >> c;
			color(find(y * S + x), c);
			//print_output();
		}
	}

int q;

	cin >> q;
	while(q--){
		int r, s, c;
		cin >> r >> s >> c;
		r--;
		s--;
		color(find(r * S + s), c);
	}
	
	print_output();
	}
	else{

	for (int y = 0; y < R; ++y)
	{
		for (int x = 0; x < S; ++x)
		{
			cout << y * S + x << endl;
			int c;
			cin >> c;
			color(find(y * S + x), c);
			//print_output();
			//cout << endl << endl;
		}
	}

	int q;

	cin >> q;
	while(q--){
		cout << q << endl;
		int r, s, c;
		cin >> r >> s >> c;
		r--;
		s--;
		if(db)	print_output();
		if(db)	cout << endl << endl;
		color(find(r * S + s), c);
			//print_output();
			//cout << endl << endl;
	}
	
	print_output();}
}

Compilation message

paint.cpp: In function 'void dfs(int, int)':
paint.cpp:119:6: warning: unused variable 'c1' [-Wunused-variable]
  119 |  int c1 = col[v];
      |      ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 6 ms 6380 KB Output is correct
3 Correct 13 ms 6636 KB Output is correct
4 Correct 23 ms 6892 KB Output is correct
5 Execution timed out 3074 ms 124116 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 52.0

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