Submission #222550

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222550	2020-04-13T10:06:30 Z	compilers	None (KOI17_civilization)	C++14	100 / 100	856 ms	30136 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(int c)
{
	int&	ret = parent[c];
	
	if( ret != c )
	{
		ret = find_parent(ret);
	}
	
	return	ret;
}

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;
				 
				adj_row = current_row+adj[d].d_row;
				adj_col = current_col+adj[d].d_col;
				
				if( !IN_RANGE(1,adj_row,N) || !IN_RANGE(1,adj_col,N) )
				{
					continue;
				}
				
				current_civilization = find_parent(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;
				
				adj_row = current_row+adj[d].d_row;
				adj_col = current_col+adj[d].d_col;
				
				if( !IN_RANGE(1,adj_row,N) || !IN_RANGE(1,adj_col,N) || grid[adj_row][adj_col]==NONE )
				{
					continue;
				}
				
				current_civilization = find_parent(grid[current_row][current_col]);
				adj_civilization = find_parent(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;
			
			adj_row = current_row+adj[d].d_row;
			adj_col = current_col+adj[d].d_col;
			
			if( !IN_RANGE(1,adj_row,N) || !IN_RANGE(1,adj_col,N) || grid[adj_row][adj_col]==NONE )
			{
				continue;
			}
			
			current_civilization = find_parent(grid[current_row][current_col]);
			adj_civilization = find_parent(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:59: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	5 ms	512 KB	Output is correct
5	Correct	5 ms	640 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	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	6 ms	768 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	5 ms	640 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	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	57 ms	8152 KB	Output is correct
13	Correct	48 ms	7288 KB	Output is correct
14	Correct	55 ms	7676 KB	Output is correct
15	Correct	38 ms	6776 KB	Output is correct
16	Correct	12 ms	3200 KB	Output is correct
17	Correct	182 ms	15052 KB	Output is correct
18	Correct	177 ms	14968 KB	Output is correct
19	Correct	179 ms	14968 KB	Output is correct
20	Correct	182 ms	14968 KB	Output is correct
21	Correct	180 ms	14968 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	61 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	6 ms	768 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	5 ms	640 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	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	57 ms	8152 KB	Output is correct
13	Correct	48 ms	7288 KB	Output is correct
14	Correct	55 ms	7676 KB	Output is correct
15	Correct	38 ms	6776 KB	Output is correct
16	Correct	12 ms	3200 KB	Output is correct
17	Correct	182 ms	15052 KB	Output is correct
18	Correct	177 ms	14968 KB	Output is correct
19	Correct	179 ms	14968 KB	Output is correct
20	Correct	182 ms	14968 KB	Output is correct
21	Correct	180 ms	14968 KB	Output is correct
22	Correct	7 ms	4352 KB	Output is correct
23	Correct	61 ms	8192 KB	Output is correct
24	Correct	186 ms	13816 KB	Output is correct
25	Correct	240 ms	16240 KB	Output is correct
26	Correct	142 ms	15224 KB	Output is correct
27	Correct	169 ms	14200 KB	Output is correct
28	Correct	118 ms	13944 KB	Output is correct
29	Correct	723 ms	25656 KB	Output is correct
30	Correct	620 ms	20376 KB	Output is correct
31	Correct	814 ms	30116 KB	Output is correct
32	Correct	838 ms	30136 KB	Output is correct
33	Correct	856 ms	29992 KB	Output is correct
34	Correct	202 ms	16120 KB	Output is correct
35	Correct	7 ms	4352 KB	Output is correct
36	Correct	5 ms	768 KB	Output is correct