Submission #489639

#TimeUsernameProblemLanguageResultExecution timeMemory
489639rainboyPaprike (COI18_paprike)C11
100 / 100
57 ms14744 KiB
#include <stdio.h> #include <stdlib.h> #define N 100000 unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int *ej[N], eo[N]; void append(int i, int j) { int o = eo[i]++; if (o >= 2 && (o & o - 1) == 0) ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); ej[i][o] = j; } int aa[N], a_; 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) if (aa[ii[j]] == aa[i_]) j++; else if (aa[ii[j]] < aa[i_]) { 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; } } int cnt; void dfs(int p, int i) { int o; for (o = eo[i]; o--; ) { int j = ej[i][o]; if (j != p) dfs(i, j); } sort(ej[i], 0, eo[i]); for (o = 0; o < eo[i]; o++) { int j = ej[i][o]; if (j != p) { if (aa[i] + aa[j] <= a_) aa[i] += aa[j]; else cnt++; } } } int main() { int n, h, i, j; scanf("%d%d", &n, &a_); for (i = 0; i < n; i++) ej[i] = (int *) malloc(2 * sizeof *ej[i]); for (i = 0; i < n; i++) scanf("%d", &aa[i]); for (h = 0; h < n - 1; h++) { scanf("%d%d", &i, &j), i--, j--; append(i, j), append(j, i); } dfs(-1, 0); printf("%d\n", cnt); return 0; }

Compilation message (stderr)

paprike.c: In function 'append':
paprike.c:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
paprike.c: In function 'main':
paprike.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &a_);
      |  ^~~~~~~~~~~~~~~~~~~~~~
paprike.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
paprike.c:76:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d", &i, &j), 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...