제출 #479381

#제출 시각아이디문제언어결과실행 시간메모리
479381rainboyTransport (COCI19_transport)C11
130 / 130
269 ms19628 KiB
#include <stdio.h> #include <stdlib.h> #define N 100000 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; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int ij[N], ww[N]; int *eh[N], eo[N], vv[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 ans; void remove_(int i, int h) { int o; for (o = eo[i]; o--; ) if (eh[i][o] == h) { eo[i]--; while (o < eo[i]) eh[i][o] = eh[i][o + 1], o++; } } int sz[N], c; void dfs(int p, int i, int n) { int o, centroid; sz[i] = 1, centroid = 1; for (o = eo[i]; o--; ) { int h = eh[i][o], j = i ^ ij[h]; if (j != p) { dfs(i, j, n); if (sz[j] * 2 > n) centroid = 0; sz[i] += sz[j]; } } if ((n - sz[i]) * 2 > n) centroid = 0; if (centroid) c = i; } int rr[N]; long long xx[N * 2]; int ii[N * 2], n_; void dfs_(int r, int p, int i, long long w, long long x, long long y) { int o; rr[i] = r; xx[i << 1 | 0] = x == w ? w - vv[c] : -1, ii[n_++] = i << 1 | 0; xx[i << 1 | 1] = -y, ii[n_++] = i << 1 | 1; for (o = eo[i]; o--; ) { int h = eh[i][o], j = i ^ ij[h]; if (j != p) dfs_(i == c ? j : r, i, j, w - ww[h] + vv[j], max(x, w - ww[h] + vv[j]), min(y, w - ww[h])); } } void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) { int c = xx[ii[j]] != xx[i_] ? (xx[ii[j]] > xx[i_] ? -1 : 1) : (ii[j] & 1) - (i_ & 1); if (c == 0) j++; else if (c < 0) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } } sort(ii, l, i); l = k; } } void cd(int i, int n) { static int kk[N]; int o, h, j, k; dfs(-1, i, n), i = c; n_ = 0; dfs_(i, -1, i, vv[i], vv[i], 0); sort(ii, 0, n_); for (h = 0, k = 0; h < n_; h++) { int i_ = ii[h]; if ((i_ & 1) == 0) kk[rr[i_ >> 1]]++, k++; else ans += k - kk[rr[i_ >> 1]]; } for (h = 0; h < n_; h++) { int i_ = ii[h]; if ((i_ & 1) == 0) kk[rr[i_ >> 1]]--; } for (o = eo[i]; o--; ) { h = eh[i][o], j = i ^ ij[h]; remove_(j, h), cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]); } } int main() { int n, h, i, j; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &vv[i]); eh[i] = (int *) malloc(2 * sizeof *eh[i]); } for (h = 0; h < n - 1; h++) { int w; scanf("%d%d%d", &i, &j, &w), i--, j--; ij[h] = i ^ j, ww[h] = w; append(i, h), append(j, h); } cd(0, n); printf("%lld\n", ans); return 0; }

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

transport.c: In function 'append':
transport.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
transport.c: In function 'main':
transport.c:130:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
transport.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d", &vv[i]);
      |   ^~~~~~~~~~~~~~~~~~~
transport.c:138:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |   scanf("%d%d%d", &i, &j, &w), 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...