oj.uz

Submission #121430

# Submission time Handle Problem Language Result Execution time Memory
121430 2019-06-26T14:04:51 Z impri None (KOI17_civilization) C++14
54 / 100
 1000 ms 67704 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 < 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: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;
      ^~~~~

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 3 ms 1920 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 3 ms 2048 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 3 ms 1280 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 3 ms 1536 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 3 ms 2048 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 4 ms 1920 KB Output is correct
12 Correct 118 ms 23756 KB Output is correct
13 Correct 90 ms 23032 KB Output is correct
14 Correct 120 ms 23436 KB Output is correct
15 Correct 82 ms 23444 KB Output is correct
16 Correct 22 ms 18048 KB Output is correct
17 Correct 315 ms 34800 KB Output is correct
18 Correct 332 ms 34720 KB Output is correct
19 Correct 334 ms 34888 KB Output is correct
20 Correct 393 ms 34780 KB Output is correct
21 Correct 328 ms 34892 KB Output is correct
22 Correct 16 ms 16000 KB Output is correct
23 Correct 91 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 3 ms 1536 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 4 ms 1664 KB Output is correct
5 Correct 3 ms 2048 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 4 ms 2048 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 4 ms 2048 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 4 ms 1920 KB Output is correct
12 Correct 118 ms 23756 KB Output is correct
13 Correct 90 ms 23032 KB Output is correct
14 Correct 120 ms 23436 KB Output is correct
15 Correct 82 ms 23444 KB Output is correct
16 Correct 22 ms 18048 KB Output is correct
17 Correct 315 ms 34800 KB Output is correct
18 Correct 332 ms 34720 KB Output is correct
19 Correct 334 ms 34888 KB Output is correct
20 Correct 393 ms 34780 KB Output is correct
21 Correct 328 ms 34892 KB Output is correct
22 Correct 16 ms 16000 KB Output is correct
23 Correct 91 ms 25848 KB Output is correct
24 Correct 312 ms 46912 KB Output is correct
25 Correct 388 ms 47376 KB Output is correct
26 Correct 262 ms 42744 KB Output is correct
27 Correct 330 ms 47188 KB Output is correct
28 Correct 212 ms 41764 KB Output is correct
29 Execution timed out 1078 ms 67704 KB Time limit exceeded
30 Halted 0 ms 0 KB -