oj.uz

Submission #705308

# Submission time Handle Problem Language Result Execution time Memory
705308 2023-03-03T22:06:04 Z rainboy Soccer (JOI17_soccer) C
100 / 100
 441 ms 106984 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	500
#define M	500
#define N_	((N + 1) * (M + 1) * 3)
#define K	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

int min(int a, int b) { return a < b ? a : b; }

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

void append(int i, int j, long long 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] = (long long *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

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

int main() {
	static int ii[K], jj[K], dd[N + 1][M + 1];
	int n, m, n_, k, h, i, j, a, b, c, o;

	scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &c, &k), n_ = (n + 1) * (m + 1) * 3;
	for (h = 0; h < k; h++)
		scanf("%d%d", &ii[h], &jj[h]);
	for (i = 0; i <= n; i++)
		memset(dd[i], 0x3f, (m + 1) * sizeof *dd[i]);
	for (h = 0; h < k; h++)
		dd[ii[h]][jj[h]] = 0;
	for (i = 0; i <= n; i++) {
		for (j = 1; j <= m; j++)
			dd[i][j] = min(dd[i][j], dd[i][j - 1] + 1);
		for (j = m - 1; j >= 0; j--)
			dd[i][j] = min(dd[i][j], dd[i][j + 1] + 1);
	}
	for (j = 0; j <= m; j++) {
		for (i = 1; i <= n; i++)
			dd[i][j] = min(dd[i][j], dd[i - 1][j] + 1);
		for (i = n - 1; i >= 0; i--)
			dd[i][j] = min(dd[i][j], dd[i + 1][j] + 1);
	}
	for (i = 0; i < n_; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ew[i] = (long long *) malloc(2 * sizeof *ew[i]);
	}
	for (i = 0; i <= n; i++)
		for (j = 0; j <= m; j++) {
			if (j > 0)
				append((i * (m + 1) + j) * 3 + 1, (i * (m + 1) + (j - 1)) * 3 + 1, a);
			if (j < m)
				append((i * (m + 1) + j) * 3 + 1, (i * (m + 1) + (j + 1)) * 3 + 1, a);
			if (i > 0)
				append((i * (m + 1) + j) * 3 + 2, ((i - 1) * (m + 1) + j) * 3 + 2, a);
			if (i < n)
				append((i * (m + 1) + j) * 3 + 2, ((i + 1) * (m + 1) + j) * 3 + 2, a);
			append((i * (m + 1) + j) * 3 + 0, (i * (m + 1) + j) * 3 + 1, b);
			append((i * (m + 1) + j) * 3 + 0, (i * (m + 1) + j) * 3 + 2, b);
			append((i * (m + 1) + j) * 3 + 1, (i * (m + 1) + j) * 3 + 0, (long long) c * dd[i][j]);
			append((i * (m + 1) + j) * 3 + 2, (i * (m + 1) + j) * 3 + 0, (long long) c * dd[i][j]);
			if (j > 0)
				append((i * (m + 1) + j) * 3 + 0, (i * (m + 1) + (j - 1)) * 3 + 0, c);
			if (j < m)
				append((i * (m + 1) + j) * 3 + 0, (i * (m + 1) + (j + 1)) * 3 + 0, c);
			if (i > 0)
				append((i * (m + 1) + j) * 3 + 0, ((i - 1) * (m + 1) + j) * 3 + 0, c);
			if (i < n)
				append((i * (m + 1) + j) * 3 + 0, ((i + 1) * (m + 1) + j) * 3 + 0, c);
		}
	memset(dd_, 0x3f, n_ * sizeof *dd_);
	i = (ii[0] * (m + 1) + jj[0]) * 3 + 0;
	dd_[i] = 0, pq_add_last(i);
	while (cnt) {
		i = pq_remove_first();
		if (i / 3 == ii[k - 1] * (m + 1) + jj[k - 1]) {
			printf("%lld\n", dd_[i]);
			return 0;
		}
		for (o = eo[i]; o--; ) {
			long long w, d;

			j = ej[i][o], w = ew[i][o], d = dd_[i] + w;
			if (dd_[j] > d) {
				if (dd_[j] == INF)
					pq_add_last(j);
				dd_[j] = d, pq_up(j);
			}
		}
	}
	return 0;
}

Compilation message

soccer.c: In function 'append':
soccer.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
soccer.c: In function 'main':
soccer.c:66:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &c, &k), n_ = (n + 1) * (m + 1) * 3;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.c:68:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d", &ii[h], &jj[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 26080 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 262 ms 105568 KB Output is correct
4 Correct 188 ms 104840 KB Output is correct
5 Correct 97 ms 38816 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 105280 KB Output is correct
2 Correct 169 ms 105172 KB Output is correct
3 Correct 246 ms 84704 KB Output is correct
4 Correct 435 ms 105516 KB Output is correct
5 Correct 274 ms 84908 KB Output is correct
6 Correct 389 ms 105832 KB Output is correct
7 Correct 261 ms 105640 KB Output is correct
8 Correct 284 ms 105792 KB Output is correct
9 Correct 172 ms 105036 KB Output is correct
10 Correct 45 ms 18180 KB Output is correct
11 Correct 376 ms 105852 KB Output is correct
12 Correct 361 ms 106012 KB Output is correct
13 Correct 295 ms 84792 KB Output is correct
14 Correct 237 ms 105548 KB Output is correct
15 Correct 140 ms 84300 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 26080 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 262 ms 105568 KB Output is correct
4 Correct 188 ms 104840 KB Output is correct
5 Correct 97 ms 38816 KB Output is correct
6 Correct 193 ms 105280 KB Output is correct
7 Correct 169 ms 105172 KB Output is correct
8 Correct 246 ms 84704 KB Output is correct
9 Correct 435 ms 105516 KB Output is correct
10 Correct 274 ms 84908 KB Output is correct
11 Correct 389 ms 105832 KB Output is correct
12 Correct 261 ms 105640 KB Output is correct
13 Correct 284 ms 105792 KB Output is correct
14 Correct 172 ms 105036 KB Output is correct
15 Correct 45 ms 18180 KB Output is correct
16 Correct 376 ms 105852 KB Output is correct
17 Correct 361 ms 106012 KB Output is correct
18 Correct 295 ms 84792 KB Output is correct
19 Correct 237 ms 105548 KB Output is correct
20 Correct 140 ms 84300 KB Output is correct
21 Correct 73 ms 37960 KB Output is correct
22 Correct 397 ms 105492 KB Output is correct
23 Correct 439 ms 94916 KB Output is correct
24 Correct 370 ms 105464 KB Output is correct
25 Correct 396 ms 105824 KB Output is correct
26 Correct 406 ms 105628 KB Output is correct
27 Correct 273 ms 105772 KB Output is correct
28 Correct 408 ms 106608 KB Output is correct
29 Correct 441 ms 106708 KB Output is correct
30 Correct 285 ms 106476 KB Output is correct
31 Correct 225 ms 105472 KB Output is correct
32 Correct 322 ms 106984 KB Output is correct
33 Correct 382 ms 105876 KB Output is correct
34 Correct 182 ms 104956 KB Output is correct
35 Correct 357 ms 106484 KB Output is correct