Submission #834123

#TimeUsernameProblemLanguageResultExecution timeMemory
834123rainboyAesthetic (NOI20_aesthetic)C11
60 / 100
401 ms32864 KiB
#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 (stderr)

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--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...