oj.uz

Submission #532336

# Submission time Handle Problem Language Result Execution time Memory
532336 2022-03-02T17:49:17 Z rainboy None (JOI14_ho_t4) C
100 / 100
 203 ms 17844 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long max(long long a, long long b) { return a > b ? a : b; }

int *ej[N], *et[N], eo[N];

void append(int i, int j, int t) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		et[i] = (int *) realloc(et[i], o * 2 * sizeof *et[i]);
	}
	ej[i][o] = j, et[i][o] = t;
}

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;
}

int main() {
	static int hh[N];
	int n, m, x, h, i, j, t;

	scanf("%d%d%d", &n, &m, &x);
	for (i = 0; i < n; i++)
		scanf("%d", &hh[i]);
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		et[i] = (int *) malloc(2 * sizeof *et[i]);
	}
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &i, &j, &t), i--, j--;
		if (hh[i] >= t)
			append(i, j, t);
		if (hh[j] >= t)
			append(j, i, t);
	}
	memset(dd, 0x3f, n * sizeof *dd);
	dd[0] = 0, pq_add_last(0);
	while (cnt) {
		int o;

		i = pq_remove_first();
		if (i == n - 1) {
			printf("%lld\n", dd[i] * 2 + (hh[i] - x));
			return 0;
		}
		for (o = eo[i]; o--; ) {
			long long d;

			j = ej[i][o], d = max(dd[i] + et[i][o], x - hh[j]);
			if (dd[j] > d) {
				if (dd[j] == INF)
					pq_add_last(j);
				dd[j] = d, pq_up(j);
			}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message

2014_ho_t4.c: In function 'append':
2014_ho_t4.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
2014_ho_t4.c: In function 'main':
2014_ho_t4.c:63:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%d%d", &n, &m, &x);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.c:65:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d", &hh[i]);
      |   ^~~~~~~~~~~~~~~~~~~
2014_ho_t4.c:71:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d%d%d", &i, &j, &t), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 2 ms 408 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 17056 KB Output is correct
2 Correct 144 ms 14472 KB Output is correct
3 Correct 107 ms 12952 KB Output is correct
4 Correct 157 ms 15028 KB Output is correct
5 Correct 120 ms 13612 KB Output is correct
6 Correct 5 ms 628 KB Output is correct
7 Correct 94 ms 15012 KB Output is correct
8 Correct 153 ms 16776 KB Output is correct
9 Correct 105 ms 12152 KB Output is correct
10 Correct 74 ms 12960 KB Output is correct
11 Correct 11 ms 2636 KB Output is correct
12 Correct 92 ms 8980 KB Output is correct
13 Correct 43 ms 6348 KB Output is correct
14 Correct 121 ms 15016 KB Output is correct
15 Correct 6 ms 1428 KB Output is correct
16 Correct 122 ms 13152 KB Output is correct
17 Correct 17 ms 3020 KB Output is correct
18 Correct 16 ms 4848 KB Output is correct
19 Correct 44 ms 6748 KB Output is correct
20 Correct 18 ms 4432 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 2 ms 408 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 156 ms 17056 KB Output is correct
22 Correct 144 ms 14472 KB Output is correct
23 Correct 107 ms 12952 KB Output is correct
24 Correct 157 ms 15028 KB Output is correct
25 Correct 120 ms 13612 KB Output is correct
26 Correct 5 ms 628 KB Output is correct
27 Correct 94 ms 15012 KB Output is correct
28 Correct 153 ms 16776 KB Output is correct
29 Correct 105 ms 12152 KB Output is correct
30 Correct 74 ms 12960 KB Output is correct
31 Correct 11 ms 2636 KB Output is correct
32 Correct 92 ms 8980 KB Output is correct
33 Correct 43 ms 6348 KB Output is correct
34 Correct 121 ms 15016 KB Output is correct
35 Correct 6 ms 1428 KB Output is correct
36 Correct 122 ms 13152 KB Output is correct
37 Correct 17 ms 3020 KB Output is correct
38 Correct 16 ms 4848 KB Output is correct
39 Correct 44 ms 6748 KB Output is correct
40 Correct 18 ms 4432 KB Output is correct
41 Correct 95 ms 8884 KB Output is correct
42 Correct 29 ms 9800 KB Output is correct
43 Correct 78 ms 9292 KB Output is correct
44 Correct 78 ms 8584 KB Output is correct
45 Correct 143 ms 14052 KB Output is correct
46 Correct 17 ms 10120 KB Output is correct
47 Correct 140 ms 16844 KB Output is correct
48 Correct 172 ms 17536 KB Output is correct
49 Correct 133 ms 14916 KB Output is correct
50 Correct 157 ms 15416 KB Output is correct
51 Correct 29 ms 4768 KB Output is correct
52 Correct 154 ms 12524 KB Output is correct
53 Correct 96 ms 15408 KB Output is correct
54 Correct 119 ms 13116 KB Output is correct
55 Correct 104 ms 14624 KB Output is correct
56 Correct 203 ms 17844 KB Output is correct
57 Correct 46 ms 11460 KB Output is correct
58 Correct 4 ms 924 KB Output is correct
59 Correct 94 ms 13432 KB Output is correct
60 Correct 37 ms 11588 KB Output is correct