Submission #894725

#	Time	Username	Problem	Language	Result	Execution time	Memory
894725		rainboy	물탱크 (KOI18_watertank)	C11	100 / 100	416 ms	47320 KiB

watertank

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

#define L	1000
#define W	1000
#define N	(L * W + 1)
#define M	((L + 1) * W + L * (W + 1))

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[M], jj[M], yy[M];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (yy[hh[j]] == yy[h])
				j++;
			else if (yy[hh[j]] < yy[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N], sz[N];

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

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

int main() {
	static int hh[M];
	int l, w, y_, n, m, h, h_, i, x, y, z, ans;

	scanf("%d%d%d", &l, &w, &y_);
	n = l * w + 1, m = 0;
	for (z = -1; z < l; z++)
		for (x = 0; x < w; x++) {
			scanf("%d", &y);
			if (y == -1)
				y = y_;
			ii[m] = z < 0 ? n - 1 : z * w + x, jj[m] = z + 1 == l ? n - 1 : (z + 1) * w + x, yy[m] = y, m++;
		}
	for (z = 0; z < l; z++)
		for (x = -1; x < w; x++) {
			scanf("%d", &y);
			if (y == -1)
				y = y_;
			ii[m] = x < 0 ? n - 1 : z * w + x, jj[m] = x + 1 == w ? n - 1 : z * w + (x + 1), yy[m] = y, m++;
		}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		sz[i] = 1;
	ans = l * w * y_;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		join(ii[h_], jj[h_]);
		ans -= (sz[find(n - 1)] - 1) * ((h + 1 == m ? y_ : yy[hh[h + 1]]) - yy[h_]);
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

watertank.c: In function 'main':
watertank.c:60:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d%d", &l, &w, &y_);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
watertank.c:64:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |    scanf("%d", &y);
      |    ^~~~~~~~~~~~~~~
watertank.c:71:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |    scanf("%d", &y);
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 18 / 18
• Subtask 3: 15 / 15
• Subtask 4: 21 / 21
• Subtask 5: 40 / 40