Submission #121432

# Submission time Handle Problem Language Result Execution time Memory
121432 2019-06-26T14:06:02 Z impri None (KOI17_civilization) C++14
0 / 100
1000 ms 2048 KB
#include<iostream>
#include<queue>
using namespace std;
 
int parent[4000001];
int siz[4000001];
int rank2[4000001];
int mov[4][2] = { 1,0,
0,1,
0,-1,
-1,0 };
int find(int n) {
	if (parent[n] == n)
		return n;
	else
		return parent[n] = find(parent[n]);
}
void uni(int a, int b) {
	if (find(a) == find(b))
		return;
  a=find(a);
  b=find(b);
  if(rank2[a]<rank2[b])
  {	siz[b] += siz[a];
	parent[a] = b;
  }
  else{
    siz[a] += siz[b];
	parent[b] = a;
    if(rank2[a]==rank2[b])
       rank2[a]++;
  }
}
int mapping(int a, int b) {
	return a * 2000 + b;
}
 
int val(int a, int b, int c) {
	if (a < c && b >= 0 && a >= 0 && b < c)
		return 1;
	return 0;
}
int area[2000][2000];
int main(void) {
  ios_base::sync_with_stdio(false);cin.tie(0);
	int n, k;
	cin >> n >> k;
	int civnumber = k;
	deque<pair<int, int> >q;
	int point;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			parent[mapping(i, j)] = mapping(i, j);
			siz[mapping(i, j)] = 1;
		}
	}
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		point = mapping(a - 1, b - 1);
		q.push_back({ a-1,b-1 });
		area[a - 1][b - 1] = 1;
		
		
	}
	int year = 0;
	while (1) {
		
		for(int j=0;j<q.size();j++) {
			int a = q[j].first;
			int b = q[j].second;
			
			for (int i = 0; i < 2; i++) {
				int nexta = a + mov[i][0];
				int nextb = b + mov[i][1];
				if (val(nexta, nextb, n) && area[nexta][nextb] ) {
					uni(mapping(nexta,nextb),mapping(a,b));
				}
			}
		}
		if (siz[find(point)] == civnumber) {
			cout << year;
			return 0;
		}
		int siz2 = q.size();
		for (int i = 0; i < siz2; i++) {
			int a = q.front().first;
			int b = q.front().second;
	
			q.pop_front();
			for (int j = 0; j < 4; j++) {
				int nexta = a + mov[j][0];
				int nextb = b + mov[j][1];
				if (val(nexta, nextb, n) && area[nexta][nextb] == 0) {
					q.push_back({ nexta,nextb });
					civnumber++;
					area[nexta][nextb] = 1;
				}
			}
		}
		year++;
 
	}
 
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<q.size();j++) {
               ~^~~~~~~~~
civilization.cpp:16:20: warning: 'point' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return parent[n] = find(parent[n]);
          ~~~~~~~~~~^~~~~~~~~~~~~~~~~
civilization.cpp:50:6: note: 'point' was declared here
  int point;
      ^~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -