Submission #545886

#	Time	Username	Problem	Language	Result	Execution time	Memory
545886		rainboy	Wall (CEOI14_wall)	C11	100 / 100	533 ms	68584 KiB

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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40