oj.uz

답안 #545886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545886 2022-04-05T15:53:18 Z rainboy Wall (CEOI14_wall) C
100 / 100
 533 ms 68584 KB 
/* http://ceoi.inf.elte.hu/probarch/14/wall-spoiler.pdf */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	400
#define M	400
#define N_	((N + 1) * (M + 1) * 4)
#define INF	0x3f3f3f3f3f3f3f3fLL

int *ej[N_], *ew[N_], eo[N_];

void append(int i, int j, int w) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

void add(int i, int j, int w) {
	append(i, j, w), append(j, i, w);
}

long long dd[N_]; int iq[1 + N_], pq[N_], cnt;

int lt(int i, int j) { return dd[i] < dd[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

void update(int i, long long d) {
	if (dd[i] > d) {
		if (dd[i] == INF)
			pq_add_last(i);
		dd[i] = d, pq_up(i);
	}
}

int qu[N_], cnt_;

void dijkstra(int n, int s) {
	memset(dd, 0x3f, n * sizeof *dd);
	dd[s] = 0, pq_add_last(s);
	cnt_ = 0;
	while (cnt) {
		int i = pq_remove_first(), o;

		qu[cnt_++] = i;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o], d = dd[i] + ew[i][o];

			if (dd[j] > d) {
				if (dd[j] == INF)
					pq_add_last(j);
				dd[j] = d, pq_up(j);
			}
		}
	}
}

int main() {
	static int used[N + 1][M + 1], cc1[N][M + 1], cc2[N + 1][M];
	static char used1[N][M + 1], used2[N + 1][M];
	int n, m, n_, i, i_, j;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &used[i][j]);
	n_ = (n + 1) * (m + 1);
	for (i_ = 0; i_ < n_; i_++) {
		ej[i_] = (int *) malloc(2 * sizeof *ej[i_]);
		ew[i_] = (int *) malloc(2 * sizeof *ew[i_]);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j <= m; j++) {
			scanf("%d", &cc1[i][j]);
			add(i * (m + 1) + j, (i + 1) * (m + 1) + j, cc1[i][j]);
		}
	for (i = 0; i <= n; i++)
		for (j = 0; j < m; j++) {
			scanf("%d", &cc2[i][j]);
			add(i * (m + 1) + j, i * (m + 1) + j + 1, cc2[i][j]);
		}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (used[i][j])
				used1[i][j] = used1[i][j + 1] = used2[i][j] = used2[i + 1][j] = 1;
	dijkstra(n_, 0 * (m + 1) + 0);
	while (cnt_--) {
		int j_ = qu[cnt_], i1 = j_ / (m + 1), j1 = j_ % (m + 1);

		if (used[i1][j1]) {
			int o;

			for (o = eo[j_]; o--; ) {
				int i_ = ej[j_][o], w = ew[j_][o];

				if (dd[i_] + w == dd[j_]) {
					int i2 = i_ / (m + 1), j2 = i_ % (m + 1);

					used[i2][j2] = 1;
					if (i2 == i1 - 1)
						used1[i1 - 1][j1] = 1;
					else if (i2 == i1 + 1)
						used1[i1][j1] = 1;
					else if (j2 == j1 - 1)
						used2[i1][j1 - 1] = 1;
					else
						used2[i1][j1] = 1;
					break;
				}
			}
		}
	}
	for (i_ = 0; i_ < n_; i_++)
		free(ej[i_]), free(ew[i_]), eo[i_] = 0;
	n_ *= 4;
	for (i_ = 0; i_ < n_; i_++) {
		ej[i_] = (int *) malloc(2 * sizeof *ej[i_]);
		ew[i_] = (int *) malloc(2 * sizeof *ew[i_]);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j <= m; j++) {
			add((i * (m + 1) + j) * 4 + 2, ((i + 1) * (m + 1) + j) * 4 + 0, cc1[i][j]);
			add((i * (m + 1) + j) * 4 + 3, ((i + 1) * (m + 1) + j) * 4 + 1, cc1[i][j]);
			if (!used1[i][j]) {
				add((i * (m + 1) + j) * 4 + 2, (i * (m + 1) + j) * 4 + 3, 0);
				add(((i + 1) * (m + 1) + j) * 4 + 0, ((i + 1) * (m + 1) + j) * 4 + 1, 0);
			}
		}
	for (i = 0; i <= n; i++)
		for (j = 0; j < m; j++) {
			add((i * (m + 1) + j) * 4 + 1, (i * (m + 1) + j + 1) * 4 + 0, cc2[i][j]);
			add((i * (m + 1) + j) * 4 + 3, (i * (m + 1) + j + 1) * 4 + 2, cc2[i][j]);
			if (!used2[i][j]) {
				add((i * (m + 1) + j) * 4 + 1, (i * (m + 1) + j) * 4 + 3, 0);
				add((i * (m + 1) + j + 1) * 4 + 0, (i * (m + 1) + j + 1) * 4 + 2, 0);
			}
		}
	for (i = 0; i <= n; i++)
		for (j = 0; j <= m; j++) {
			if (i == 0 && j == 0)
				continue;
			if (i == 0)
				add((i * (m + 1) + j) * 4 + 0, (i * (m + 1) + j) * 4 + 1, 0);
			if (i == n)
				add((i * (m + 1) + j) * 4 + 2, (i * (m + 1) + j) * 4 + 3, 0);
			if (j == 0)
				add((i * (m + 1) + j) * 4 + 0, (i * (m + 1) + j) * 4 + 2, 0);
			if (j == m)
				add((i * (m + 1) + j) * 4 + 1, (i * (m + 1) + j) * 4 + 3, 0);
		}
	dijkstra(n_, (0 * (m + 1) + 0) * 4 + 1);
	printf("%lld\n", dd[(0 * (m + 1) + 0) * 4 + 2]);
	return 0;
}

Compilation message

wall.c: In function 'append':
wall.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
wall.c: In function 'main':
wall.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
wall.c:102:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |    scanf("%d", &used[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~
wall.c:110:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |    scanf("%d", &cc1[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~
wall.c:115:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |    scanf("%d", &cc2[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 3 ms 1064 KB Output is correct
13 Correct 4 ms 1248 KB Output is correct
14 Correct 4 ms 1068 KB Output is correct
15 Correct 3 ms 980 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1204 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1200 KB Output is correct
6 Correct 3 ms 1200 KB Output is correct
7 Correct 3 ms 1200 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 3 ms 1180 KB Output is correct
10 Correct 3 ms 1236 KB Output is correct
11 Correct 4 ms 1200 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 2 ms 1200 KB Output is correct
14 Correct 3 ms 1236 KB Output is correct
15 Correct 4 ms 1200 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 3 ms 1108 KB Output is correct
18 Correct 3 ms 1108 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 17408 KB Output is correct
2 Correct 64 ms 15012 KB Output is correct
3 Correct 75 ms 16200 KB Output is correct
4 Correct 89 ms 14988 KB Output is correct
5 Correct 134 ms 38264 KB Output is correct
6 Correct 78 ms 17440 KB Output is correct
7 Correct 175 ms 40292 KB Output is correct
8 Correct 187 ms 39712 KB Output is correct
9 Correct 176 ms 39416 KB Output is correct
10 Correct 251 ms 40016 KB Output is correct
11 Correct 260 ms 40668 KB Output is correct
12 Correct 60 ms 17248 KB Output is correct
13 Correct 185 ms 38108 KB Output is correct
14 Correct 233 ms 60608 KB Output is correct
15 Correct 329 ms 66504 KB Output is correct
16 Correct 355 ms 67488 KB Output is correct
17 Correct 490 ms 67992 KB Output is correct
18 Correct 533 ms 68584 KB Output is correct
19 Correct 411 ms 66680 KB Output is correct
20 Correct 329 ms 66632 KB Output is correct