oj.uz

Submission #121387

# Submission time Handle Problem Language Result Execution time Memory
121387 2019-06-26T13:11:10 Z impri None (KOI17_civilization) C++14
54 / 100
 1000 ms 67520 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) {
	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 < 4; 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:68: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:49:6: note: 'point' was declared here
  int point;
      ^~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2048 KB Output is correct
2 Correct 3 ms 1792 KB Output is correct
3 Correct 4 ms 2048 KB Output is correct
4 Correct 4 ms 2048 KB Output is correct
5 Correct 4 ms 2048 KB Output is correct
6 Correct 4 ms 2176 KB Output is correct
7 Correct 4 ms 2176 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct
11 Correct 4 ms 2048 KB Output is correct
12 Correct 4 ms 2048 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2048 KB Output is correct
2 Correct 3 ms 1792 KB Output is correct
3 Correct 4 ms 2048 KB Output is correct
4 Correct 4 ms 2048 KB Output is correct
5 Correct 4 ms 2048 KB Output is correct
6 Correct 4 ms 2176 KB Output is correct
7 Correct 4 ms 2176 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct
11 Correct 4 ms 2048 KB Output is correct
12 Correct 153 ms 31452 KB Output is correct
13 Correct 122 ms 29952 KB Output is correct
14 Correct 157 ms 30712 KB Output is correct
15 Correct 132 ms 28508 KB Output is correct
16 Correct 43 ms 19832 KB Output is correct
17 Correct 428 ms 34680 KB Output is correct
18 Correct 467 ms 34712 KB Output is correct
19 Correct 458 ms 34940 KB Output is correct
20 Correct 518 ms 34620 KB Output is correct
21 Correct 518 ms 34636 KB Output is correct
22 Correct 15 ms 16000 KB Output is correct
23 Correct 83 ms 31608 KB Output is correct
24 Correct 4 ms 2048 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2048 KB Output is correct
2 Correct 3 ms 1792 KB Output is correct
3 Correct 4 ms 2048 KB Output is correct
4 Correct 4 ms 2048 KB Output is correct
5 Correct 4 ms 2048 KB Output is correct
6 Correct 4 ms 2176 KB Output is correct
7 Correct 4 ms 2176 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct
11 Correct 4 ms 2048 KB Output is correct
12 Correct 153 ms 31452 KB Output is correct
13 Correct 122 ms 29952 KB Output is correct
14 Correct 157 ms 30712 KB Output is correct
15 Correct 132 ms 28508 KB Output is correct
16 Correct 43 ms 19832 KB Output is correct
17 Correct 428 ms 34680 KB Output is correct
18 Correct 467 ms 34712 KB Output is correct
19 Correct 458 ms 34940 KB Output is correct
20 Correct 518 ms 34620 KB Output is correct
21 Correct 518 ms 34636 KB Output is correct
22 Correct 15 ms 16000 KB Output is correct
23 Correct 83 ms 31608 KB Output is correct
24 Correct 436 ms 62016 KB Output is correct
25 Correct 533 ms 63148 KB Output is correct
26 Correct 349 ms 53668 KB Output is correct
27 Correct 419 ms 62484 KB Output is correct
28 Correct 269 ms 51092 KB Output is correct
29 Execution timed out 1082 ms 67520 KB Time limit exceeded
30 Halted 0 ms 0 KB -