Submission #222568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222568	2020-04-13T11:06:26 Z	compilers	None (KOI17_civilization)	C++14	100 / 100	874 ms	29224 KB

civilization

#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;
}

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;
}

bool	merge_civilization(int current_row,int current_col,int adj_row,int adj_col)
{
	int	current_civilization,adj_civilization;
	
	current_civilization = find_parent_civilization(grid[current_row][current_col]);
	adj_civilization = find_parent_civilization(grid[adj_row][adj_col]);
	
	if( adj_civilization==NONE || current_civilization==adj_civilization )
	{
		return	false;
	}
	
	int	big,small;
				
	big = max(current_civilization,adj_civilization);
	small = min(current_civilization,adj_civilization);
	parent[big] = small;
	
	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,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]);
				
				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;
				
				if( get_adj_pos(current_row,current_col,adj_row,adj_col,d) == false )
				{
					continue;
				}
				
				if( merge_civilization(current_row,current_col,adj_row,adj_col) == true )
				{
					K--;
				}
			}
		}
		/*
		cout<<"time="<<t+1<<",K="<<K<<'\n';
		
		for(int row=1;row<=N;row++)
		{
			for(int col=1;col<=N;col++)
			{
				cout<<find_parent(grid[row][col])<<' ';
			}
			cout<<'\n';
		}
		getchar();
		*/
	}
	
	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;
			
			if( get_adj_pos(current_row,current_col,adj_row,adj_col,d) == false )
			{
				continue;
			}
			
			if( merge_civilization(current_row,current_col,adj_row,adj_col) == true )
			{
				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;
}

Compilation message

civilization.cpp: In function 'int simulate(std::queue<std::pair<int, int> >&)':
civilization.cpp:94:30: warning: unused variable 'adj_civilization' [-Wunused-variable]
     int current_civilization,adj_civilization;
                              ^~~~~~~~~~~~~~~~

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	5 ms	640 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	5 ms	768 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	5 ms	768 KB	Output is correct

Subtask #2

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	5 ms	640 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	5 ms	768 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	67 ms	8184 KB	Output is correct
13	Correct	53 ms	7228 KB	Output is correct
14	Correct	66 ms	7672 KB	Output is correct
15	Correct	46 ms	6780 KB	Output is correct
16	Correct	13 ms	3200 KB	Output is correct
17	Correct	179 ms	14200 KB	Output is correct
18	Correct	183 ms	14200 KB	Output is correct
19	Correct	185 ms	14200 KB	Output is correct
20	Correct	188 ms	14200 KB	Output is correct
21	Correct	198 ms	14312 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	66 ms	8192 KB	Output is correct
24	Correct	5 ms	768 KB	Output is correct

Subtask #3

46.0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	5 ms	640 KB	Output is correct
5	Correct	6 ms	768 KB	Output is correct
6	Correct	5 ms	768 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	67 ms	8184 KB	Output is correct
13	Correct	53 ms	7228 KB	Output is correct
14	Correct	66 ms	7672 KB	Output is correct
15	Correct	46 ms	6780 KB	Output is correct
16	Correct	13 ms	3200 KB	Output is correct
17	Correct	179 ms	14200 KB	Output is correct
18	Correct	183 ms	14200 KB	Output is correct
19	Correct	185 ms	14200 KB	Output is correct
20	Correct	188 ms	14200 KB	Output is correct
21	Correct	198 ms	14312 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	66 ms	8192 KB	Output is correct
24	Correct	195 ms	13816 KB	Output is correct
25	Correct	263 ms	16036 KB	Output is correct
26	Correct	154 ms	15224 KB	Output is correct
27	Correct	190 ms	14156 KB	Output is correct
28	Correct	135 ms	13944 KB	Output is correct
29	Correct	805 ms	25148 KB	Output is correct
30	Correct	696 ms	20120 KB	Output is correct
31	Correct	862 ms	29224 KB	Output is correct
32	Correct	864 ms	29124 KB	Output is correct
33	Correct	874 ms	29096 KB	Output is correct
34	Correct	205 ms	16120 KB	Output is correct
35	Correct	7 ms	4352 KB	Output is correct
36	Correct	5 ms	768 KB	Output is correct