oj.uz

Submission #222553

# Submission time Handle Problem Language Result Execution time Memory
222553 2020-04-13T10:18:41 Z compilers None (KOI17_civilization) C++14
0 / 100
 1000 ms 310420 KB 
#include	<iostream>
#include	<queue>

using namespace	std;

#define	MAX_SIZE			(2000+1)
#define	MAX_CIVILIZATION	(100000+1)
#define	NONE				0

#define	UP		0
#define	DOWN	1
#define	LEFT	2
#define	RIGHT	3
#define	MAX_DIR	4

const struct{
	int	d_row,d_col;
} adj[MAX_DIR] = {{-1,0},{1,0},{0,-1},{0,1}};

#define	IN_RANGE(MIN,n,MAX)	((MIN)<=(n)&&(n)<=(MAX))

typedef	pair<int,int>	Pos;	// first:row, second:col

int	N,K,grid[MAX_SIZE][MAX_SIZE];
int	parent[MAX_CIVILIZATION];

int		find_parent_civilization(int c)
{
	int&	ret = parent[c];
	
	if( ret != c )
	{
		ret = find_parent_civilization(ret);
	}
	
	return	ret;
}

void	merge_civilization(int c1,int c2)
{
	int	big,small;
				
	big = max(c1,c2);
	small = min(c1,c2);
	parent[big] = small;
}

bool	get_adj_pos(const int& current_row,const int& current_col,
					int& adj_row,int& adj_col,const int& direction)
{
	adj_row = current_row+adj[direction].d_row;
	adj_col = current_col+adj[direction].d_col;
	
	if( !IN_RANGE(1,adj_row,N) || !IN_RANGE(1,adj_col,N) )
	{
		return	false;
	}
	
	return	true;
}

int		simulate(queue<Pos>& pos_q)
{
	int	t;
	
	for(t=0;K!=1;t++)
	{
		queue<Pos>	spread;
		
		for(int i=1,size=pos_q.size();i<=size;i++)
		{
			int	current_row,current_col;
			
			current_row = pos_q.front().first;
			current_col = pos_q.front().second;
						
			pos_q.pop();
			
			for(int d=UP;d<=RIGHT;d++)
			{
				int	adj_row,adj_col;
				int	current_civilization;
				
				if( get_adj_pos(current_row,current_col,adj_row,adj_col,d) == false )
				{
					continue;
				} 
				
				current_civilization = find_parent_civilization(grid[current_row][current_col]);
				
				if( grid[adj_row][adj_col] == NONE )
				{
					grid[adj_row][adj_col] = current_civilization;
					spread.push(make_pair(adj_row,adj_col));
					pos_q.push(make_pair(adj_row,adj_col));
				}
			}
		}
		
		for(;!spread.empty();)
		{
			int	current_row,current_col;
			
			current_row = spread.front().first;
			current_col = spread.front().second;
			
			spread.pop();
			
			for(int d=UP;d<=RIGHT;d++)
			{
				int	adj_row,adj_col;
				int	current_civilization,adj_civilization;
				
				if( get_adj_pos(current_row,current_col,adj_row,adj_col,d) == false )
				{
					continue;
				}
				
				current_civilization = find_parent_civilization(grid[current_row][current_col]);
				adj_civilization = find_parent_civilization(grid[adj_row][adj_col]);
				
				if( current_civilization == adj_civilization )
				{
					continue;
				}
				
				merge_civilization(current_civilization,adj_civilization);
				K--;
			}
		}
	}
	
	return	t;	
}

void	input(queue<Pos>& pos_q)
{
	cin>>N>>K;
	
	for(int i=1;i<=K;i++)
	{
		int	row,col;

		cin>>col>>row;
		pos_q.push(make_pair(row,col));
		grid[row][col] = parent[i] = i;
	}
	
	for(int i=1,size=pos_q.size();i<=size;i++)
	{
		int	current_row,current_col;
		
		current_row = pos_q.front().first;
		current_col = pos_q.front().second;
		
		pos_q.pop();
		pos_q.push(make_pair(current_row,current_col));
		
		for(int d=UP;d<=RIGHT;d++)
		{
			int	adj_row,adj_col;
			int	current_civilization,adj_civilization;
			
			if( get_adj_pos(current_row,current_col,adj_row,adj_col,d) == false )
			{
				continue;
			}
			
			current_civilization = find_parent_civilization(grid[current_row][current_col]);
			adj_civilization = find_parent_civilization(grid[adj_row][adj_col]);
			
			if( current_civilization != adj_civilization )
			{
				merge_civilization(current_civilization,adj_civilization);
				K--;
			}
		}
	}
}

int		main(void)
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	
	queue<Pos>	pos_q;
	
	input(pos_q);
	cout<<simulate(pos_q)<<'\n';
	
	return	0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 310420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 310420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1115 ms 310420 KB Time limit exceeded
2 Halted 0 ms 0 KB -