Submission #920591

#	Time	Username	Problem	Language	Result	Execution time	Memory
920591		rainboy	문명 (KOI17_civilization)	C++17	100 / 100	505 ms	68948 KiB

civilization

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	2000
#define M	100000

int max(int a, int b) { return a > b ? a : b; }

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int *eu[N], *ev[N], eo[N];

void append(int d, int u, int v) {
	int o = eo[d]++;

	if (o >= 2 && (o & o - 1) == 0) {
		eu[d] = (int *) realloc(eu[d], o * 2 * sizeof *eu[d]);
		ev[d] = (int *) realloc(ev[d], o * 2 * sizeof *ev[d]);
	}
	eu[d][o] = u, ev[d][o] = v;
}

int ds[M];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int main() {
	static int dd[N][N], uu[N][N], qu[N * N];
	int n, m, cnt, g, h, i, i_, j, j_, ij, ij_, u, v, d, o, k;

	scanf("%d%d", &n, &m);
	if (m == 1) {
		printf("0\n");
		return 0;
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			dd[i][j] = n * 2 + 1;
	cnt = 0;
	for (u = 0; u < m; u++) {
		scanf("%d%d", &i, &j), i--, j--;
		dd[i][j] = 0, uu[i][j] = u, qu[cnt++] = i * n + j;
	}
	for (h = 0; h < cnt; h++) {
		ij = qu[h], i = ij / n, j = ij % n, d = dd[i][j] + 1, u = uu[i][j];
		for (g = 0; g < 4; g++) {
			i_ = i + di[g], j_ = j + dj[g], ij_ = i_ * n + j_;
			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < n && dd[i_][j_] > d)
				dd[i_][j_] = d, uu[i_][j_] = u, qu[cnt++] = ij_;
		}
	}
	for (d = 0; d < n; d++) {
		eu[d] = (int *) malloc(2 * sizeof *eu[d]);
		ev[d] = (int *) malloc(2 * sizeof *ev[d]);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			u = uu[i][j];
			for (g = 0; g < 4; g += 2) {
				i_ = i + di[g], j_ = j + dj[g], v = uu[i_][j_];
				if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < n && u != v) {
					d = max(dd[i][j], dd[i_][j_]);
					if (d < n)
						append(d, u, v);
				}
			}
		}
	memset(ds, -1, m * sizeof *ds);
	k = m;
	for (d = 0; d < n; d++)
		for (o = eo[d]; o--; ) {
			u = eu[d][o], v = ev[d][o];
			if (join(u, v) && --k == 1) {
				printf("%d\n", d);
				return 0;
			}
		}
	return 0;
}

Compilation message (stderr)

civilization.cpp: In function 'void append(int, int, int)':
civilization.cpp:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
civilization.cpp: In function 'int main()':
civilization.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
civilization.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d%d", &i, &j), i--, j--;
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 35 / 35
• Subtask 3: 46 / 46