oj.uz

Submission #832772

# Submission time Handle Problem Language Result Execution time Memory
832772 2023-08-21T14:45:45 Z rainboy Relay Marathon (NOI20_relaymarathon) C
25 / 100
 1888 ms 66356 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define M	3000000
#define INF	0x3f3f3f3f

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

char special[N]; int n;
int ii[M], jj[M], ww[M], m;

int *eh[N], eo[N];

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

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int dd[N], rr[N], 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(int i) {
	pq[i] = ++cnt, pq_up(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 dijkstra() {
	int i, o;

	memset(pq, 0, n * sizeof *pq), cnt = 0;
	for (i = 0; i < n; i++)
		pq_add(i);
	while (cnt) {
		i = pq_remove_first();
		for (o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ii[h] ^ jj[h], d = dd[i] + ww[h];

			if (dd[j] > d)
				dd[j] = d, rr[j] = rr[i], pq_up(j);
		}
	}
}

int main() {
	int k, h, i, i_, i1, j, j_, j1, w, d, d1, d2, di1, di2, dj1, dj2, ans;

	scanf("%d%d%d", &n, &m, &k);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &i, &j, &w), i--, j--;
		ii[h] = i, jj[h] = j, ww[h] = w;
		append(i, h), append(j, h);
	}
	while (k--) {
		scanf("%d", &i), i--;
		special[i] = 1;
	}
	for (i = 0; i < n; i++)
		dd[i] = special[i] ? 0 : INF, rr[i] = i;
	dijkstra();
	d1 = INF, i_ = j_ = -1;
	for (h = 0; h < m; h++) {
		i = ii[h], j = jj[h];
		if (rr[i] != rr[j] && d1 > (d = dd[i] + ww[h] + dd[j]))
			d1 = d, i_ = rr[i], j_ = rr[j];
	}
	for (i = 0; i < n; i++)
		dd[i] = special[i] && i != i_ && i != j_ ? 0 : INF, rr[i] = i;
	dijkstra();
	d2 = INF, i_ = j_ = -1;
	for (h = 0; h < m; h++) {
		i = ii[h], j = jj[h];
		if (rr[i] != rr[j])
			d2 = min(d2, dd[i] + ww[h] + dd[j]);
	}
	ans = d1 + d2;
	for (i = 0; i < n; i++)
		dd[i] = i == i_ ? 0 : INF, rr[i] = i;
	dijkstra();
	di1 = di2 = INF, j1 = -1;
	for (j = 0; j < n; j++)
		if (special[j] && j != i_ && j != j_) {
			if (di1 > dd[j])
				di2 = di1, di1 = dd[j], j1 = j;
			else if (di2 > dd[j])
				di2 = dd[j];
		}
	for (i = 0; i < n; i++)
		dd[i] = i == j_ ? 0 : INF, rr[i] = i;
	dijkstra();
	dj1 = dj2 = INF, i1 = -1;
	for (i = 0; i < n; i++)
		if (special[i] && i != i_ && i != j_) {
			if (dj1 > dd[i])
				dj2 = dj1, dj1 = dd[i], i1 = i;
			else if (dj2 > dd[i])
				dj2 = dd[i];
		}
	if (i1 != j1)
		ans = min(ans, di1 + dj1);
	else
		ans = min(ans, min(di1 + dj2, di2 + dj1));
	printf("%d\n", ans);
	return 0;
}

Compilation message

RelayMarathon.c: In function 'append':
RelayMarathon.c:19:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   19 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
RelayMarathon.c: In function 'main':
RelayMarathon.c:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d%d", &i, &j, &w), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.c:90:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8036 KB Output is correct
2 Correct 11 ms 6440 KB Output is correct
3 Correct 1726 ms 62152 KB Output is correct
4 Correct 660 ms 29460 KB Output is correct
5 Correct 162 ms 10108 KB Output is correct
6 Correct 155 ms 9240 KB Output is correct
7 Correct 170 ms 10724 KB Output is correct
8 Correct 88 ms 7988 KB Output is correct
9 Correct 130 ms 8928 KB Output is correct
10 Correct 86 ms 8268 KB Output is correct
11 Correct 1723 ms 64908 KB Output is correct
12 Correct 85 ms 8404 KB Output is correct
13 Correct 397 ms 20024 KB Output is correct
14 Correct 171 ms 10724 KB Output is correct
15 Correct 1651 ms 63680 KB Output is correct
16 Correct 58 ms 7864 KB Output is correct
17 Correct 1126 ms 44404 KB Output is correct
18 Correct 17 ms 6440 KB Output is correct
19 Correct 1888 ms 66356 KB Output is correct
20 Correct 150 ms 10332 KB Output is correct
21 Correct 155 ms 9788 KB Output is correct
22 Correct 78 ms 8280 KB Output is correct
23 Correct 35 ms 7376 KB Output is correct
24 Correct 1059 ms 49432 KB Output is correct
25 Correct 143 ms 9020 KB Output is correct
26 Correct 85 ms 7948 KB Output is correct
27 Correct 112 ms 8576 KB Output is correct
28 Correct 20 ms 6924 KB Output is correct
29 Correct 139 ms 10552 KB Output is correct
30 Correct 338 ms 16232 KB Output is correct

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 292 KB Output isn't correct
2 Halted 0 ms 0 KB -