Submission #222564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222564	2020-04-13T11:00:00 Z	compilers	None (KOI17_civilization)	C++14	100 / 100	862 ms	29100 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 )
				{
					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--;
			}
		}
		/*
		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	6 ms	768 KB	Output is correct
4	Correct	6 ms	640 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	6 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	12 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	6 ms	768 KB	Output is correct
4	Correct	6 ms	640 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	6 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	62 ms	8188 KB	Output is correct
13	Correct	44 ms	7296 KB	Output is correct
14	Correct	56 ms	7672 KB	Output is correct
15	Correct	39 ms	6880 KB	Output is correct
16	Correct	12 ms	3176 KB	Output is correct
17	Correct	189 ms	14232 KB	Output is correct
18	Correct	188 ms	14176 KB	Output is correct
19	Correct	201 ms	14200 KB	Output is correct
20	Correct	246 ms	14328 KB	Output is correct
21	Correct	201 ms	14280 KB	Output is correct
22	Correct	9 ms	4352 KB	Output is correct
23	Correct	58 ms	8192 KB	Output is correct
24	Correct	12 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	6 ms	768 KB	Output is correct
4	Correct	6 ms	640 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	6 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	62 ms	8188 KB	Output is correct
13	Correct	44 ms	7296 KB	Output is correct
14	Correct	56 ms	7672 KB	Output is correct
15	Correct	39 ms	6880 KB	Output is correct
16	Correct	12 ms	3176 KB	Output is correct
17	Correct	189 ms	14232 KB	Output is correct
18	Correct	188 ms	14176 KB	Output is correct
19	Correct	201 ms	14200 KB	Output is correct
20	Correct	246 ms	14328 KB	Output is correct
21	Correct	201 ms	14280 KB	Output is correct
22	Correct	9 ms	4352 KB	Output is correct
23	Correct	58 ms	8192 KB	Output is correct
24	Correct	181 ms	13816 KB	Output is correct
25	Correct	222 ms	15992 KB	Output is correct
26	Correct	137 ms	15224 KB	Output is correct
27	Correct	170 ms	14204 KB	Output is correct
28	Correct	140 ms	13920 KB	Output is correct
29	Correct	762 ms	25372 KB	Output is correct
30	Correct	597 ms	20088 KB	Output is correct
31	Correct	826 ms	29100 KB	Output is correct
32	Correct	818 ms	29100 KB	Output is correct
33	Correct	862 ms	29096 KB	Output is correct
34	Correct	195 ms	16032 KB	Output is correct
35	Correct	7 ms	4328 KB	Output is correct
36	Correct	12 ms	768 KB	Output is correct