제출 #680448

#제출 시각아이디문제언어결과실행 시간메모리
680448rainboyWild Boar (JOI18_wild_boar)C11
0 / 100
1 ms596 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 2000 #define M 2000 #define M2 (M * 2) #define MM (M * M) #define K 6 #define L 100000 #define N_ (1 << 17) /* N_ = pow2(ceil(log2(L))) */ #define INF 0x3f3f3f3f3f3f3f3fLL long long min(long long a, long long b) { return a < b ? a : b; } unsigned int Z = 12345; int rand_() { return (Z *= 3) >> 1; } int ij[M2], cc[M], m; int *eh[N], eo[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[M2 + 1], pq[M2], 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 solve(long long *dd, int u) { static int kk[N]; int h, i, o; memset(dd, 0x3f, m * 2 * sizeof *dd), memset(kk, 0, n * sizeof *kk); dd_ = dd, dd[u] = cc[u >> 1], pq_add_last(u); while (cnt) { h = pq_remove_first(), i = ij[h ^ 1]; if (kk[i] < 2) { kk[i]++; for (o = eo[i]; o--; ) { int h_ = eh[i][o]; long long d = dd[h] + cc[h_ >> 1]; if ((h ^ h_) != 1 && dd[h_] > d) { if (dd[h_] == INF) pq_add_last(h_); dd[h_] = d, pq_up(h_); } } } } } int uu1[MM], vv1[MM]; long long ww1[MM]; int compare_uv(int h1, int h2) { return uu1[h1] != uu1[h2] ? uu1[h1] - uu1[h2] : vv1[h1] - vv1[h2]; } int compare_w(int h1, int h2) { return ww1[h1] == ww1[h2] ? 0 : (ww1[h1] < ww1[h2] ? -1 : 1); } int (*compare)(int, int); void sort(int *gg, int l, int r) { while (l < r) { int i = l, j = l, k = r, g = gg[l + rand_() % (r - l)], tmp; while (j < k) { int c = compare(gg[j], g); if (c == 0) j++; else if (c < 0) { tmp = gg[i], gg[i] = gg[j], gg[j] = tmp; i++, j++; } else { k--; tmp = gg[j], gg[j] = gg[k], gg[k] = tmp; } } sort(gg, l, i); l = k; } } int simplify(int k) { static int dd1[M2], dd2[M2], gg[MM], uu_[MM], vv_[MM]; static long long ww_[MM]; int k_, g, g_, u, v; long long w; for (g = 0; g < k; g++) gg[g] = g; compare = compare_uv, sort(gg, 0, k); k_ = 0; for (g = 0; g < k; g++) { u = uu1[gg[g]], v = vv1[gg[g]]; g_ = g, w = INF; while (g_ < k && uu1[gg[g_]] == u && vv1[gg[g_]] == v) w = min(w, ww1[gg[g_++]]); uu_[k_] = u, vv_[k_] = v, ww_[k_] = w, k_++; } memcpy(uu1, uu_, k_ * sizeof *uu_); memcpy(vv1, vv_, k_ * sizeof *vv_); memcpy(ww1, ww_, k_ * sizeof *ww_); k = k_; compare = compare_w, sort(gg, 0, k); k_ = 0; for (g = 0; g < k; g++) { g_ = gg[g], u = uu1[g_], v = vv1[g_], w = ww1[g_]; if (dd1[u] >= 2 || dd2[v] >= 2) continue; dd1[u]++, dd2[v]++; if (k_ < K) uu_[k_] = u, vv_[k_] = v, ww_[k_] = w, k_++; } for (g = 0; g < k; g++) { u = uu1[g], v = vv1[g]; dd1[u] = 0, dd2[v] = 0; } memcpy(uu1, uu_, k_ * sizeof *uu_); memcpy(vv1, vv_, k_ * sizeof *vv_); memcpy(ww1, ww_, k_ * sizeof *ww_); return k_; } int uu[N][N][K], vv[N][N][K], kk[N][N]; long long ww[N][N][K]; int uu_[N_ * 2][K], vv_[N_ * 2][K], kk_[N_ * 2], n_; long long ww_[N_ * 2][K]; void pul(int i) { int l, r, k, g1, g2; l = i << 1, r = l | 1; if (kk_[l] == -1 && kk_[r] == -1) kk_[i] = -1; else if (kk_[r] == -1) { memcpy(uu_[i], uu_[l], kk_[l] * sizeof *uu_[l]); memcpy(vv_[i], vv_[l], kk_[l] * sizeof *vv_[l]); memcpy(ww_[i], ww_[l], kk_[l] * sizeof *ww_[l]); kk_[i] = kk_[l]; } else if (kk_[l] == -1) { memcpy(uu_[i], uu_[r], kk_[r] * sizeof *uu_[r]); memcpy(vv_[i], vv_[r], kk_[r] * sizeof *vv_[r]); memcpy(ww_[i], ww_[r], kk_[r] * sizeof *ww_[r]); kk_[i] = kk_[r]; } else { k = 0; for (g1 = 0; g1 < kk_[l]; g1++) for (g2 = 0; g2 < kk_[r]; g2++) if ((vv_[l][g1] ^ uu_[r][g2]) != 1) uu1[k] = uu_[l][g1], vv1[k] = vv_[r][g2], ww1[k] = min(ww_[l][g1] + ww_[r][g2], INF), k++; k = simplify(k); memcpy(uu_[i], uu1, k * sizeof *uu1); memcpy(vv_[i], vv1, k * sizeof *vv1); memcpy(ww_[i], ww1, k * sizeof *ww1); kk_[i] = k; } } int ii[L], l; void build() { int h, i, j; n_ = 1; while (n_ < l) n_ <<= 1; for (h = 0; h < n_; h++) if (h + 1 < l) { i = ii[h], j = ii[h + 1]; memcpy(uu_[n_ + h], uu[i][j], kk[i][j] * sizeof *uu[i][j]); memcpy(vv_[n_ + h], vv[i][j], kk[i][j] * sizeof *vv[i][j]); memcpy(ww_[n_ + h], ww[i][j], kk[i][j] * sizeof *ww[i][j]); kk_[n_ + h] = kk[i][j]; } else kk_[n_ + h] = -1; for (h = n_ - 1; h > 0; h--) pul(h); } void upd(int h) { int i = ii[h], j = ii[h + 1]; memcpy(uu_[n_ + h], uu[i][j], kk[i][j] * sizeof *uu[i][j]); memcpy(vv_[n_ + h], vv[i][j], kk[i][j] * sizeof *vv[i][j]); memcpy(ww_[n_ + h], ww[i][j], kk[i][j] * sizeof *ww[i][j]); kk_[n_ + h] = kk[i][j]; h += n_; while (h > 1) pul(h >>= 1); } int main() { static long long dd[M2][M2]; int q, k, g, h, i, j, u, v, o, o_; scanf("%d%d%d%d", &n, &m, &q, &l); 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, &cc[h]), i--, j--; ij[h << 1 | 0] = i, ij[h << 1 | 1] = j; append(i, h << 1 | 0), append(j, h << 1 | 1); } for (u = 0; u < m * 2; u++) solve(dd[u], u); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { k = 0; for (o = eo[i]; o--; ) { u = eh[i][o]; for (o_ = eo[j]; o_--; ) { v = eh[j][o_] ^ 1; uu1[k] = u, vv1[k] = v, ww1[k] = dd[u][v], k++; } } k = simplify(k); memcpy(uu[i][j], uu1, k * sizeof *uu1); memcpy(vv[i][j], vv1, k * sizeof *vv1); memcpy(ww[i][j], ww1, k * sizeof *ww1); kk[i][j] = k; } for (h = 0; h < l; h++) scanf("%d", &ii[h]), ii[h]--; build(); while (q--) { long long ans; scanf("%d%d", &h, &i), h--, i--; ii[h] = i; if (h > 0) upd(h - 1); if (h + 1 < l) upd(h); ans = INF; for (g = 0; g < kk_[1]; g++) ans = min(ans, ww_[1][g]); printf("%lld\n", ans == INF ? -1 : ans); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

wild_boar.c: In function 'append':
wild_boar.c:28:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
wild_boar.c: In function 'main':
wild_boar.c:240:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |  scanf("%d%d%d%d", &n, &m, &q, &l);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.c:244:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |   scanf("%d%d%d", &i, &j, &cc[h]), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.c:267:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |   scanf("%d", &ii[h]), ii[h]--;
      |   ^~~~~~~~~~~~~~~~~~~
wild_boar.c:272:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |   scanf("%d%d", &h, &i), h--, i--;
      |   ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...