Submission #222560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222560	2020-04-13T10:58:14 Z	compilers	None (KOI17_civilization)	C++14	100 / 100	817 ms	29220 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;
}
 
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 
					|| grid[adj_row][adj_col]==NONE )
				{
					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;
				}
				
				int	big,small;
				
				big = max(current_civilization,adj_civilization);
				small = min(current_civilization,adj_civilization);
				
				parent[big] = small;
				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 
				|| grid[adj_row][adj_col]==NONE )
			{
				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 )
			{
				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:73: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	5 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	5 ms	768 KB	Output is correct
9	Correct	5 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	5 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	5 ms	768 KB	Output is correct
9	Correct	5 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	63 ms	8184 KB	Output is correct
13	Correct	46 ms	7288 KB	Output is correct
14	Correct	52 ms	7672 KB	Output is correct
15	Correct	39 ms	6776 KB	Output is correct
16	Correct	11 ms	3200 KB	Output is correct
17	Correct	164 ms	14200 KB	Output is correct
18	Correct	183 ms	14284 KB	Output is correct
19	Correct	178 ms	14200 KB	Output is correct
20	Correct	172 ms	14200 KB	Output is correct
21	Correct	193 ms	14328 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	65 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	5 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	5 ms	768 KB	Output is correct
9	Correct	5 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	63 ms	8184 KB	Output is correct
13	Correct	46 ms	7288 KB	Output is correct
14	Correct	52 ms	7672 KB	Output is correct
15	Correct	39 ms	6776 KB	Output is correct
16	Correct	11 ms	3200 KB	Output is correct
17	Correct	164 ms	14200 KB	Output is correct
18	Correct	183 ms	14284 KB	Output is correct
19	Correct	178 ms	14200 KB	Output is correct
20	Correct	172 ms	14200 KB	Output is correct
21	Correct	193 ms	14328 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	65 ms	8192 KB	Output is correct
24	Correct	170 ms	13944 KB	Output is correct
25	Correct	231 ms	15992 KB	Output is correct
26	Correct	137 ms	15224 KB	Output is correct
27	Correct	173 ms	14200 KB	Output is correct
28	Correct	122 ms	13948 KB	Output is correct
29	Correct	734 ms	25304 KB	Output is correct
30	Correct	596 ms	20216 KB	Output is correct
31	Correct	795 ms	29220 KB	Output is correct
32	Correct	809 ms	29064 KB	Output is correct
33	Correct	817 ms	29096 KB	Output is correct
34	Correct	184 ms	16120 KB	Output is correct
35	Correct	7 ms	4352 KB	Output is correct
36	Correct	5 ms	768 KB	Output is correct