oj.uz

Submission #132754

# Submission time Handle Problem Language Result Execution time Memory
132754 2019-07-19T13:08:44 Z abra_stone None (KOI17_civilization) C++14
100 / 100
 983 ms 34040 KB 
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 2005
#define K 100005
using namespace std;

int n, k, ans, ca[K], g[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool v[N][N];
queue<int> qx, qy, qg, qc;

int uni(int p) {
	if (ca[p] == p) return p;
	return ca[p] = uni(ca[p]);
}

void f(int x, int y, int fg, int fc) {
	if (g[x][y] == -1) return;
	if (v[x][y] == 0) {
		qx.push(x);
		qy.push(y);
		qg.push(fg);
		qc.push(fc + 1);
		v[x][y] = 1;
		return;
	}
}

int main()
{
	int i, j, t1, t2, fx, fy, fg, fc;
	cin >> n >> k;
	if (k == 1) {cout << '0' << endl; return 0;}
	for (i = 1; i <= k; i++) ca[i] = i;
	for (i = 0; i <= n + 1; i++) for (j = 0; j <= n + 1; j++) g[i][j] = -1;
	for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) g[i][j] = 0;
	for (i = 1; i <= k; i++) {
		scanf("%d %d", &fx, &fy);
		qx.push(fx);
		qy.push(fy);
		qg.push(i);
		qc.push(0);
		g[fx][fy] = i;
	}
	while (!qx.empty()) {
		fx = qx.front(), qx.pop();
		fy = qy.front(), qy.pop();
		fg = qg.front(), qg.pop();
		fc = qc.front(), qc.pop();
		g[fx][fy] = fg;
		for (i = 0; i < 4; i++) {
			if (g[fx + dx[i]][fy + dy[i]] > 0) {
				t1 = uni(g[fx + dx[i]][fy + dy[i]]);
				t2 = uni(fg);
				if (t1 != t2) {
					ca[t2] = t1;
					ans = fc;
				}
			}
		}
		for (i = 0; i < 4; i++) {
			f(fx + dx[i], fy + dy[i], fg, fc);
		}
	}
	cout << ans << endl;
    return 0;
}

Compilation message

civilization.cpp: In function 'int main()':
civilization.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &fx, &fy);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 89 ms 10204 KB Output is correct
13 Correct 90 ms 10268 KB Output is correct
14 Correct 80 ms 10192 KB Output is correct
15 Correct 89 ms 10204 KB Output is correct
16 Correct 88 ms 10232 KB Output is correct
17 Correct 252 ms 18040 KB Output is correct
18 Correct 247 ms 18168 KB Output is correct
19 Correct 253 ms 18168 KB Output is correct
20 Correct 284 ms 18272 KB Output is correct
21 Correct 291 ms 18296 KB Output is correct
22 Correct 85 ms 10232 KB Output is correct
23 Correct 82 ms 10232 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 89 ms 10204 KB Output is correct
13 Correct 90 ms 10268 KB Output is correct
14 Correct 80 ms 10192 KB Output is correct
15 Correct 89 ms 10204 KB Output is correct
16 Correct 88 ms 10232 KB Output is correct
17 Correct 252 ms 18040 KB Output is correct
18 Correct 247 ms 18168 KB Output is correct
19 Correct 253 ms 18168 KB Output is correct
20 Correct 284 ms 18272 KB Output is correct
21 Correct 291 ms 18296 KB Output is correct
22 Correct 85 ms 10232 KB Output is correct
23 Correct 82 ms 10232 KB Output is correct
24 Correct 355 ms 20188 KB Output is correct
25 Correct 379 ms 20000 KB Output is correct
26 Correct 355 ms 20204 KB Output is correct
27 Correct 398 ms 20088 KB Output is correct
28 Correct 376 ms 20116 KB Output is correct
29 Correct 843 ms 29640 KB Output is correct
30 Correct 885 ms 24388 KB Output is correct
31 Correct 983 ms 34040 KB Output is correct
32 Correct 940 ms 33976 KB Output is correct
33 Correct 925 ms 34040 KB Output is correct
34 Correct 347 ms 20048 KB Output is correct
35 Correct 354 ms 20216 KB Output is correct
36 Correct 3 ms 1016 KB Output is correct