oj.uz

Submission #121359

# Submission time Handle Problem Language Result Execution time Memory
121359 2019-06-26T12:23:13 Z impri None (KOI17_civilization) C++14
54 / 100
 1000 ms 52116 KB 
#include<iostream>
#include<queue>
using namespace std;

int parent[4000001];
int siz[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;
	siz[find(b)] += siz[find(a)];
	parent[find(a)] = find(b);
}
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:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<q.size();j++) {
               ~^~~~~~~~~
civilization.cpp:15:20: warning: 'point' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return parent[n] = find(parent[n]);
          ~~~~~~~~~~^~~~~~~~~~~~~~~~~
civilization.cpp:38:6: note: 'point' was declared here
  int point;
      ^~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 3 ms 1524 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 4 ms 1664 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 4 ms 1664 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 3 ms 1524 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 4 ms 1664 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 4 ms 1664 KB Output is correct
12 Correct 136 ms 23620 KB Output is correct
13 Correct 106 ms 22956 KB Output is correct
14 Correct 134 ms 23388 KB Output is correct
15 Correct 102 ms 22180 KB Output is correct
16 Correct 25 ms 17888 KB Output is correct
17 Correct 378 ms 27708 KB Output is correct
18 Correct 436 ms 27640 KB Output is correct
19 Correct 471 ms 27640 KB Output is correct
20 Correct 523 ms 27640 KB Output is correct
21 Correct 484 ms 27568 KB Output is correct
22 Correct 17 ms 16120 KB Output is correct
23 Correct 75 ms 23896 KB Output is correct
24 Correct 4 ms 1664 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 3 ms 1524 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 4 ms 1664 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 4 ms 1664 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 4 ms 1664 KB Output is correct
12 Correct 136 ms 23620 KB Output is correct
13 Correct 106 ms 22956 KB Output is correct
14 Correct 134 ms 23388 KB Output is correct
15 Correct 102 ms 22180 KB Output is correct
16 Correct 25 ms 17888 KB Output is correct
17 Correct 378 ms 27708 KB Output is correct
18 Correct 436 ms 27640 KB Output is correct
19 Correct 471 ms 27640 KB Output is correct
20 Correct 523 ms 27640 KB Output is correct
21 Correct 484 ms 27568 KB Output is correct
22 Correct 17 ms 16120 KB Output is correct
23 Correct 75 ms 23896 KB Output is correct
24 Correct 427 ms 46888 KB Output is correct
25 Correct 556 ms 47268 KB Output is correct
26 Correct 325 ms 42792 KB Output is correct
27 Correct 416 ms 47056 KB Output is correct
28 Correct 260 ms 41720 KB Output is correct
29 Execution timed out 1080 ms 52116 KB Time limit exceeded
30 Halted 0 ms 0 KB -