oj.uz

Submission #544616

# Submission time Handle Problem Language Result Execution time Memory
544616 2022-04-02T13:37:34 Z rainboy Portals (BOI14_portals) C
100 / 100
 817 ms 131552 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1000
#define M	1000
#define N_	(N * M)
#define INF	0x3f3f3f3f

int di[] = { 0, 0, -1, 1 };
int dj[] = { -1, 1, 0, 0 };

int *oj[N_], *ow[N_], oo[N_];

void link(int i, int j, int w) {
	int o = oo[i]++;

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

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

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

		if (i == t)
			return dd[t];
		for (o = 0; o < oo[i]; o++) {
			int j = oj[i][o], d = dd[i] + ow[i][o];

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

int main() {
	static char cc[N][M + 1];
	static int dd[N][M], qu[N * M];
	int n, m, i, j, is, js, ic, jc, head, cnt;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	head = cnt = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (i == 0 || i == n - 1 || j == 0 || j == m - 1 || cc[i][j - 1] == '#' || cc[i][j + 1] == '#' || cc[i - 1][j] == '#' || cc[i + 1][j] == '#')
				dd[i][j] = 0, qu[head + cnt++] = i * m + j;
			else
				dd[i][j] = n * m;
	while (cnt) {
		int ij, d, h;

		ij = qu[cnt--, head++], i = ij / m, j = ij % m, d = dd[i][j] + 1;
		for (h = 0; h < 4; h++) {
			int i_ = i + di[h], j_ = j + dj[h];

			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && dd[i_][j_] > d)
				dd[i_][j_] = d, qu[head + cnt++] = i_ * m + j_;
		}
	}
	for (i = 0; i < n * m; i++) {
		oj[i] = (int *) malloc(2 * sizeof *oj[i]);
		ow[i] = (int *) malloc(2 * sizeof *ow[i]);
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] != '#') {
				if (i > 0 && cc[i - 1][j] != '#') {
					link(i * m + j, (i - 1) * m + j, 1);
					link((i - 1) * m + j, i * m + j, 1);
				}
				if (j > 0 && cc[i][j - 1] != '#') {
					link(i * m + j, i * m + j - 1, 1);
					link(i * m + j - 1, i * m + j, 1);
				}
			}
	for (i = 0; i < n; i++) {
		int j_;

		for (j = 0, j_ = 0; j < m; j++)
			if (cc[i][j] == '#')
				j_ = j + 1;
			else
				link(i * m + j, i * m + j_, dd[i][j] + 1);
		for (j = m - 1, j_ = m - 1; j >= 0; j--)
			if (cc[i][j] == '#')
				j_ = j - 1;
			else
				link(i * m + j, i * m + j_, dd[i][j] + 1);
	}
	for (j = 0; j < m; j++) {
		int i_;

		for (i = 0, i_ = 0; i < n; i++)
			if (cc[i][j] == '#')
				i_ = i + 1;
			else
				link(i * m + j, i_ * m + j, dd[i][j] + 1);
		for (i = n - 1, i_ = n - 1; i >= 0; i--)
			if (cc[i][j] == '#')
				i_ = i - 1;
			else
				link(i * m + j, i_ * m + j, dd[i][j] + 1);
	}
	is = js = -1, ic = jc = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == 'S')
				is = i, js = j;
			else if (cc[i][j] == 'C')
				ic = i, jc = j;
	printf("%d\n", dijkstra(n * m, is * m + js, ic * m + jc));
	return 0;
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 424 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 0 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 13 ms 6076 KB Output is correct
6 Correct 14 ms 6060 KB Output is correct
7 Correct 13 ms 6228 KB Output is correct
8 Correct 12 ms 6396 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 396 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 12 ms 6100 KB Output is correct
15 Correct 14 ms 6096 KB Output is correct
16 Correct 17 ms 6228 KB Output is correct
17 Correct 14 ms 6100 KB Output is correct
18 Correct 16 ms 6320 KB Output is correct
19 Correct 12 ms 6340 KB Output is correct
20 Correct 16 ms 6360 KB Output is correct
21 Correct 14 ms 6064 KB Output is correct
22 Correct 14 ms 6100 KB Output is correct
23 Correct 15 ms 6100 KB Output is correct
24 Correct 19 ms 6340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 11 ms 6360 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 932 KB Output is correct
10 Correct 2 ms 928 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 13 ms 6100 KB Output is correct
15 Correct 14 ms 6168 KB Output is correct
16 Correct 14 ms 6216 KB Output is correct
17 Correct 13 ms 6084 KB Output is correct
18 Correct 15 ms 6228 KB Output is correct
19 Correct 12 ms 6228 KB Output is correct
20 Correct 17 ms 6356 KB Output is correct
21 Correct 15 ms 6072 KB Output is correct
22 Correct 13 ms 6092 KB Output is correct
23 Correct 16 ms 6216 KB Output is correct
24 Correct 518 ms 126072 KB Output is correct
25 Correct 817 ms 131552 KB Output is correct
26 Correct 379 ms 129160 KB Output is correct
27 Correct 510 ms 131392 KB Output is correct
28 Correct 411 ms 125964 KB Output is correct
29 Correct 472 ms 126760 KB Output is correct
30 Correct 462 ms 126792 KB Output is correct
31 Correct 18 ms 6356 KB Output is correct
32 Correct 617 ms 131488 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 424 ms 124884 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 11 ms 6388 KB Output is correct
38 Correct 415 ms 131312 KB Output is correct
39 Correct 325 ms 118356 KB Output is correct