Submission #222566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222566	2020-04-13T11:04:25 Z	compilers	None (KOI17_civilization)	C++14	100 / 100	886 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;
				int	current_civilization,adj_civilization;
				
				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;
			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( adj_civilization==NONE || current_civilization==adj_civilization )
			{
				continue;
			}
			
			int	big,small;
			
			big = max(current_civilization,adj_civilization);
			small = min(current_civilization,adj_civilization);
			
			parent[big] = small;
			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;
                              ^~~~~~~~~~~~~~~~
civilization.cpp:124:9: warning: unused variable 'current_civilization' [-Wunused-variable]
     int current_civilization,adj_civilization;
         ^~~~~~~~~~~~~~~~~~~~
civilization.cpp:124: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	6 ms	768 KB	Output is correct
8	Correct	5 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	6 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	6 ms	768 KB	Output is correct
8	Correct	5 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	64 ms	8184 KB	Output is correct
13	Correct	57 ms	7416 KB	Output is correct
14	Correct	65 ms	7672 KB	Output is correct
15	Correct	45 ms	6780 KB	Output is correct
16	Correct	13 ms	3200 KB	Output is correct
17	Correct	167 ms	14216 KB	Output is correct
18	Correct	184 ms	14292 KB	Output is correct
19	Correct	189 ms	14292 KB	Output is correct
20	Correct	174 ms	14200 KB	Output is correct
21	Correct	176 ms	14168 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	71 ms	8192 KB	Output is correct
24	Correct	6 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	6 ms	768 KB	Output is correct
8	Correct	5 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	64 ms	8184 KB	Output is correct
13	Correct	57 ms	7416 KB	Output is correct
14	Correct	65 ms	7672 KB	Output is correct
15	Correct	45 ms	6780 KB	Output is correct
16	Correct	13 ms	3200 KB	Output is correct
17	Correct	167 ms	14216 KB	Output is correct
18	Correct	184 ms	14292 KB	Output is correct
19	Correct	189 ms	14292 KB	Output is correct
20	Correct	174 ms	14200 KB	Output is correct
21	Correct	176 ms	14168 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	71 ms	8192 KB	Output is correct
24	Correct	208 ms	13920 KB	Output is correct
25	Correct	257 ms	15992 KB	Output is correct
26	Correct	157 ms	15224 KB	Output is correct
27	Correct	200 ms	14200 KB	Output is correct
28	Correct	135 ms	13944 KB	Output is correct
29	Correct	795 ms	25272 KB	Output is correct
30	Correct	688 ms	20184 KB	Output is correct
31	Correct	868 ms	29224 KB	Output is correct
32	Correct	851 ms	29092 KB	Output is correct
33	Correct	886 ms	29096 KB	Output is correct
34	Correct	217 ms	16120 KB	Output is correct
35	Correct	7 ms	4352 KB	Output is correct
36	Correct	6 ms	768 KB	Output is correct