oj.uz

Submission #832753

# Submission time Handle Problem Language Result Execution time Memory
832753 2023-08-21T14:29:33 Z rainboy Relay Marathon (NOI20_relaymarathon) C
25 / 100
 1180 ms 106956 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], 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, pq_up(j);
		}
	}
}

int rr[N];

void dfs(int i, int r) {
	int o;

	if (rr[i] != -1)
		return;
	rr[i] = r;
	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)
			dfs(j, r);
	}
}

int main() {
	int k, h, i, j, w, 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;
	dijkstra();
	memset(rr, -1, n * sizeof *rr);
	for (i = 0; i < n; i++)
		if (special[i])
			dfs(i, i);
	ans = INF;
	for (h = 0; h < m; h++)
		if (ii[h] != 0 && jj[h] != 0 && rr[ii[h]] != rr[jj[h]])
			ans = min(ans, dd[ii[h]] + ww[h] + dd[jj[h]] + 1);
	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:97:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.c:101:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d%d%d", &i, &j, &w), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.c:106:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   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 38 ms 8220 KB Output is correct
2 Correct 7 ms 6448 KB Output is correct
3 Correct 1029 ms 100064 KB Output is correct
4 Correct 483 ms 43380 KB Output is correct
5 Correct 85 ms 11860 KB Output is correct
6 Correct 75 ms 10256 KB Output is correct
7 Correct 94 ms 12752 KB Output is correct
8 Correct 41 ms 8304 KB Output is correct
9 Correct 64 ms 9832 KB Output is correct
10 Correct 55 ms 8812 KB Output is correct
11 Correct 1169 ms 104932 KB Output is correct
12 Correct 54 ms 9100 KB Output is correct
13 Correct 222 ms 28436 KB Output is correct
14 Correct 93 ms 12872 KB Output is correct
15 Correct 1087 ms 102932 KB Output is correct
16 Correct 29 ms 7816 KB Output is correct
17 Correct 678 ms 68496 KB Output is correct
18 Correct 8 ms 6484 KB Output is correct
19 Correct 1180 ms 106956 KB Output is correct
20 Correct 94 ms 12164 KB Output is correct
21 Correct 83 ms 11320 KB Output is correct
22 Correct 47 ms 8608 KB Output is correct
23 Correct 15 ms 7380 KB Output is correct
24 Correct 699 ms 76532 KB Output is correct
25 Correct 66 ms 9896 KB Output is correct
26 Correct 39 ms 8264 KB Output is correct
27 Correct 59 ms 9176 KB Output is correct
28 Correct 15 ms 6916 KB Output is correct
29 Correct 90 ms 12528 KB Output is correct
30 Correct 185 ms 21732 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 -