oj.uz

Submission #121375

# Submission time Handle Problem Language Result Execution time Memory
121375 2019-06-26T13:06:08 Z impri None (KOI17_civilization) C++14
54 / 100
 1000 ms 67452 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;
  if(rank2[find(a)]<rank2[find(b)])
  {	siz[find(b)] += siz[find(a)];
	parent[find(a)] = find(b);
  }
  else{
    siz[find(a)] += siz[find(b)];
	parent[find(b)] = find(a);
    if(rank2[find(a)]==rank2[find(b)])
       rank2[find(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:66: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:47: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 4 ms 1536 KB Output is correct
3 Correct 4 ms 1792 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 5 ms 2048 KB Output is correct
6 Correct 4 ms 2048 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 4 ms 2048 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 4 ms 1920 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 4 ms 1536 KB Output is correct
3 Correct 4 ms 1792 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 5 ms 2048 KB Output is correct
6 Correct 4 ms 2048 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 4 ms 2048 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 4 ms 1920 KB Output is correct
12 Correct 140 ms 23800 KB Output is correct
13 Correct 93 ms 23036 KB Output is correct
14 Correct 129 ms 23364 KB Output is correct
15 Correct 87 ms 23416 KB Output is correct
16 Correct 24 ms 17912 KB Output is correct
17 Correct 353 ms 34592 KB Output is correct
18 Correct 387 ms 34624 KB Output is correct
19 Correct 406 ms 34636 KB Output is correct
20 Correct 401 ms 34656 KB Output is correct
21 Correct 380 ms 34680 KB Output is correct
22 Correct 15 ms 16128 KB Output is correct
23 Correct 73 ms 25848 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 4 ms 1536 KB Output is correct
3 Correct 4 ms 1792 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 5 ms 2048 KB Output is correct
6 Correct 4 ms 2048 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 4 ms 2048 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 4 ms 1920 KB Output is correct
12 Correct 140 ms 23800 KB Output is correct
13 Correct 93 ms 23036 KB Output is correct
14 Correct 129 ms 23364 KB Output is correct
15 Correct 87 ms 23416 KB Output is correct
16 Correct 24 ms 17912 KB Output is correct
17 Correct 353 ms 34592 KB Output is correct
18 Correct 387 ms 34624 KB Output is correct
19 Correct 406 ms 34636 KB Output is correct
20 Correct 401 ms 34656 KB Output is correct
21 Correct 380 ms 34680 KB Output is correct
22 Correct 15 ms 16128 KB Output is correct
23 Correct 73 ms 25848 KB Output is correct
24 Correct 337 ms 47104 KB Output is correct
25 Correct 418 ms 47352 KB Output is correct
26 Correct 271 ms 42744 KB Output is correct
27 Correct 335 ms 47096 KB Output is correct
28 Correct 216 ms 41720 KB Output is correct
29 Execution timed out 1077 ms 67452 KB Time limit exceeded
30 Halted 0 ms 0 KB -