Submission #545886

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545886	2022-04-05T15:53:18 Z	rainboy	Wall (CEOI14_wall)	C	100 / 100	533 ms	68584 KB

wall

/* 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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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