oj.uz

Submission #834123

# Submission time Handle Problem Language Result Execution time Memory
834123 2023-08-22T10:58:08 Z rainboy Aesthetic (NOI20_aesthetic) C
60 / 100
 401 ms 32864 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define M	300000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int ii[M], jj[M], ww[M]; char path[M]; int m;
int *eh[N], eo[N]; long long dds[N], ddt[N]; int ff[N], gg[N], 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;
}

long long *dd; 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;
}

void dijkstra(int n, int s) {
	int i, o;

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

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

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

	gg[i] = l;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
		long long d = dds[i] + ww[h];

		if (dds[j] == d && gg[j] == -1)
			dfs(j, l);
	}
}

long long st[N_ * 2]; int n_;

void update(int l, int r, int x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = min(st[l], x), l++;
		if ((r & 1) == 0)
			st[r] = min(st[r], x), r--;
	}
}

int main() {
	static int qu[N];
	int g, h, i, j, l, r, tmp, w;
	long long ans;

	scanf("%d%d", &n, &m);
	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, &ww[h]), i--, j--;
		ii[h] = i, jj[h] = j;
		append(i, h), append(j, h);
	}
	dd = dds, dijkstra(n, 0);
	dd = ddt, dijkstra(n, n - 1);
	i = 0, cnt = 0;
	while (i != n - 1) {
		qu[cnt++] = i;
		h = ff[i];
		path[h] = 1, i ^= ii[h] ^ jj[h];
	}
	qu[cnt++] = i;
	memset(gg, -1, n * sizeof *gg);
	for (g = 0; g < cnt; g++)
		gg[qu[g]] = g;
	for (g = 0; g < cnt; g++)
		dfs(qu[g], g);
	n_ = 1;
	while (n_ < cnt)
		n_ <<= 1;
	memset(st, 0x3f, n_ * 2 * sizeof *st);
	for (h = 0; h < m; h++)
		if (!path[h]) {
			i = ii[h], j = jj[h], l = gg[i], r = gg[j];
			if (l > r)
				tmp = i, i = j, j = tmp, tmp = l, l = r, r = tmp;
			if (l < r)
				update(l, r - 1, dds[i] + ww[h] + ddt[j]);
		}
	for (i = 1; i < n_; i++) {
		st[i << 1 | 0] = min(st[i << 1 | 0], st[i]);
		st[i << 1 | 1] = min(st[i << 1 | 1], st[i]);
	}
	w = 0, ans = dds[n - 1];
	for (h = m - 1; h >= 0; h--) {
		if (path[h]) {
			g = min(gg[ii[h]], gg[jj[h]]);
			ans = max(ans, min(dds[n - 1] + w, st[n_ + g]));
		}
		w = max(w, ww[h]);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 24908 KB Output is correct
2 Correct 401 ms 31704 KB Output is correct
3 Correct 391 ms 31332 KB Output is correct
4 Correct 392 ms 31280 KB Output is correct
5 Correct 385 ms 31388 KB Output is correct
6 Correct 399 ms 32208 KB Output is correct
7 Correct 389 ms 32028 KB Output is correct
8 Correct 354 ms 32240 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 25428 KB Output is correct
2 Correct 360 ms 31568 KB Output is correct
3 Correct 370 ms 31780 KB Output is correct
4 Correct 380 ms 32076 KB Output is correct
5 Correct 373 ms 31436 KB Output is correct
6 Correct 358 ms 31788 KB Output is correct
7 Correct 387 ms 31596 KB Output is correct
8 Correct 393 ms 31804 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 19572 KB Output is correct
2 Correct 120 ms 27192 KB Output is correct
3 Correct 119 ms 17484 KB Output is correct
4 Correct 113 ms 17524 KB Output is correct
5 Correct 115 ms 17392 KB Output is correct
6 Correct 124 ms 17488 KB Output is correct
7 Correct 111 ms 17472 KB Output is correct
8 Correct 114 ms 17552 KB Output is correct
9 Correct 112 ms 17484 KB Output is correct
10 Correct 124 ms 17656 KB Output is correct
11 Correct 111 ms 17480 KB Output is correct
12 Correct 242 ms 23680 KB Output is correct
13 Correct 114 ms 17556 KB Output is correct
14 Correct 102 ms 32836 KB Output is correct
15 Correct 107 ms 32864 KB Output is correct
16 Correct 219 ms 23484 KB Output is correct
17 Correct 237 ms 22868 KB Output is correct
18 Correct 223 ms 23264 KB Output is correct
19 Correct 124 ms 27332 KB Output is correct
20 Correct 124 ms 27320 KB Output is correct
21 Correct 122 ms 27352 KB Output is correct
22 Correct 123 ms 27316 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 19572 KB Output is correct
2 Correct 120 ms 27192 KB Output is correct
3 Correct 119 ms 17484 KB Output is correct
4 Correct 113 ms 17524 KB Output is correct
5 Correct 115 ms 17392 KB Output is correct
6 Correct 124 ms 17488 KB Output is correct
7 Correct 111 ms 17472 KB Output is correct
8 Correct 114 ms 17552 KB Output is correct
9 Correct 112 ms 17484 KB Output is correct
10 Correct 124 ms 17656 KB Output is correct
11 Correct 111 ms 17480 KB Output is correct
12 Correct 242 ms 23680 KB Output is correct
13 Correct 114 ms 17556 KB Output is correct
14 Correct 102 ms 32836 KB Output is correct
15 Correct 107 ms 32864 KB Output is correct
16 Correct 219 ms 23484 KB Output is correct
17 Correct 237 ms 22868 KB Output is correct
18 Correct 223 ms 23264 KB Output is correct
19 Correct 124 ms 27332 KB Output is correct
20 Correct 124 ms 27320 KB Output is correct
21 Correct 122 ms 27352 KB Output is correct
22 Correct 123 ms 27316 KB Output is correct
23 Correct 276 ms 23760 KB Output is correct
24 Correct 139 ms 27296 KB Output is correct
25 Correct 120 ms 17544 KB Output is correct
26 Correct 131 ms 17540 KB Output is correct
27 Correct 115 ms 17508 KB Output is correct
28 Correct 118 ms 17632 KB Output is correct
29 Correct 121 ms 17660 KB Output is correct
30 Correct 139 ms 17620 KB Output is correct
31 Correct 128 ms 17780 KB Output is correct
32 Correct 127 ms 17488 KB Output is correct
33 Correct 121 ms 17692 KB Output is correct
34 Correct 250 ms 23472 KB Output is correct
35 Correct 117 ms 17736 KB Output is correct
36 Correct 86 ms 24200 KB Output is correct
37 Correct 91 ms 24860 KB Output is correct
38 Correct 282 ms 23552 KB Output is correct
39 Correct 257 ms 23216 KB Output is correct
40 Correct 271 ms 23780 KB Output is correct
41 Correct 140 ms 27432 KB Output is correct
42 Correct 135 ms 27324 KB Output is correct
43 Correct 133 ms 27328 KB Output is correct
44 Correct 134 ms 27408 KB Output is correct

Subtask #7
0 / 27.0

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