Submission #722680

#	Time	Username	Problem	Language	Result	Execution time	Memory
722680		rainboy	Sirtet (CCO19_day1problem2)	C11	25 / 25	272 ms	119788 KiB

Main

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

#define NM	1000000
#define INF	0x3f3f3f3f

int *ev[NM + 1], *ew[NM + 1], eo[NM + 1];

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

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

int dd[NM + 1], iq[NM + 2], pq[NM + 1], 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;
}

int main() {
	static char cc[NM], cc_[NM + 1];
	int n, m, i, i_, j, u, v, o;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc + i * m);
	for (u = 0; u <= n * m; u++) {
		ev[u] = (int *) malloc(2 * sizeof *ev[u]);
		ew[u] = (int *) malloc(2 * sizeof *ew[u]);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[u = i * m + j] == '#') {
				if (i > 0 && cc[v = (i - 1) * m + j] == '#')
					append(u, v, 0), append(v, u, 0);
				if (j > 0 && cc[v = i * m + (j - 1)] == '#')
					append(u, v, 0), append(v, u, 0);
			}
	for (j = 0; j < m; j++)
		for (i = n - 1, i_ = n, v = n * m; i >= 0; i--)
			if (cc[u = i * m + j] == '#')
				append(v, u, i_ - i - 1), i_ = i, v = u;
	memset(dd, 0x3f, (n * m + 1) * sizeof *dd);
	dd[n * m] = 0, pq_add_last(n * m);
	while (cnt) {
		u = pq_remove_first();
		for (o = eo[u]; o--; ) {
			int w, d;

			v = ev[u][o], w = ew[u][o], d = dd[u] + w;
			if (dd[v] > d) {
				if (dd[v] == INF)
					pq_add_last(v);
				dd[v] = d, pq_up(v);
			}
		}
	}
	memset(cc_, '.', n * m * sizeof *cc_);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[u = i * m + j] == '#')
				cc_[(i + dd[u]) * m + j] = '#';
	for (i = 0; i < n; i++) {
		char c = cc_[(i + 1) * m];

		cc_[(i + 1) * m] = 0;
		printf("%s\n", cc_ + i * m);
		cc_[(i + 1) * m] = c;
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Main.c: In function 'main':
Main.c:63:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:65:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%s", cc + i * m);
      |   ^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9