oj.uz

Submission #121363

# Submission time Handle Problem Language Result Execution time Memory
121363 2019-06-26T12:29:22 Z impri None (KOI17_civilization) C++14
54 / 100
 1000 ms 51760 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;
   if(siz[find(b)]>siz[find(a)])
   {siz[find(a)] += siz[find(b)];
	parent[find(b)] = find(a);}
  else
      {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:62: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:43:6: note: 'point' was declared here
  int point;
      ^~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1664 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 5 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 3 ms 1664 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 3 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 3 ms 1664 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 5 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 3 ms 1664 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 3 ms 1664 KB Output is correct
12 Correct 143 ms 23760 KB Output is correct
13 Correct 108 ms 22904 KB Output is correct
14 Correct 149 ms 23428 KB Output is correct
15 Correct 100 ms 22268 KB Output is correct
16 Correct 26 ms 17920 KB Output is correct
17 Correct 431 ms 26760 KB Output is correct
18 Correct 470 ms 27000 KB Output is correct
19 Correct 489 ms 26856 KB Output is correct
20 Correct 450 ms 26872 KB Output is correct
21 Correct 476 ms 26872 KB Output is correct
22 Correct 14 ms 16000 KB Output is correct
23 Correct 76 ms 23928 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 3 ms 1664 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 5 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 3 ms 1664 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 3 ms 1664 KB Output is correct
12 Correct 143 ms 23760 KB Output is correct
13 Correct 108 ms 22904 KB Output is correct
14 Correct 149 ms 23428 KB Output is correct
15 Correct 100 ms 22268 KB Output is correct
16 Correct 26 ms 17920 KB Output is correct
17 Correct 431 ms 26760 KB Output is correct
18 Correct 470 ms 27000 KB Output is correct
19 Correct 489 ms 26856 KB Output is correct
20 Correct 450 ms 26872 KB Output is correct
21 Correct 476 ms 26872 KB Output is correct
22 Correct 14 ms 16000 KB Output is correct
23 Correct 76 ms 23928 KB Output is correct
24 Correct 443 ms 47104 KB Output is correct
25 Correct 636 ms 47364 KB Output is correct
26 Correct 343 ms 42756 KB Output is correct
27 Correct 483 ms 47252 KB Output is correct
28 Correct 274 ms 41720 KB Output is correct
29 Execution timed out 1079 ms 51760 KB Time limit exceeded
30 Halted 0 ms 0 KB -