Submission #796768

#TimeUsernameProblemLanguageResultExecution timeMemory
796768rainboyPaths (RMI21_paths)C11
100 / 100
208 ms17644 KiB
#include <stdio.h> #include <stdlib.h> #define N 100000 #define INF 0x3f3f3f3f3f3f3f3fLL int *ej[N], *ew[N], eo[N], jj[N], n, k; long long ans[N]; void append(int i, int j, int w) { int o = eo[i]++; if (o >= 2 && (o & o - 1) == 0) { ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]); } ej[i][o] = j, ew[i][o] = w; } long long cc[N], sum; int pq[2][N], iq[2][N + 1], cnt[2], mode; int lt(int i, int j) { return mode == 0 ? cc[i] < cc[j] : cc[i] > cc[j]; } int p2(int p) { return (p *= 2) > cnt[mode] ? 0 : (p < cnt[mode] && lt(iq[mode][p + 1], iq[mode][p]) ? p + 1 : p); } void pq_up(int i) { int p, q, j; for (p = pq[mode][i]; (q = p / 2) && lt(i, j = iq[mode][q]); p = q) iq[mode][pq[mode][j] = p] = j; iq[mode][pq[mode][i] = p] = i; } void pq_dn(int i) { int p, q, j; for (p = pq[mode][i]; (q = p2(p)) && lt(j = iq[mode][q], i); p = q) iq[mode][pq[mode][j] = p] = j; iq[mode][pq[mode][i] = p] = i; } void pq_add(int i) { pq[mode][i] = ++cnt[mode], pq_up(i); } int pq_first() { return iq[mode][1]; } void pq_remove(int i) { int j = iq[mode][cnt[mode]--]; if (j != i) pq[mode][j] = pq[mode][i], pq_up(j), pq_dn(j); pq[mode][i] = 0; } void add(int i) { mode = 0; pq_add(i), sum += cc[i]; if (cnt[0] > k) { i = pq_first(); pq_remove(i), sum -= cc[i]; mode = 1; pq_add(i); } } void remove_(int i) { if (pq[1][i]) { mode = 1; pq_remove(i); } else { mode = 0; pq_remove(i), sum -= cc[i]; mode = 1; if (cnt[1]) { i = pq_first(); pq_remove(i); mode = 0; pq_add(i), sum += cc[i]; } } } void dfs1(int p, int i) { int o; jj[i] = -1; for (o = eo[i]; o--; ) { int j = ej[i][o], w = ew[i][o]; if (j != p) { dfs1(i, j); cc[j] += w; if (jj[i] == -1 || cc[jj[i]] < cc[j]) jj[i] = j; } } cc[i] = jj[i] == -1 ? 0 : cc[jj[i]]; for (o = eo[i]; o--; ) { int j = ej[i][o]; if (j != p && j != jj[i]) add(j); } } void dfs2(int p, int i) { int o, j1, j2, k; long long c; c = cc[i]; ans[i] = sum; if (eo[i] == 1) return; j1 = -1, j2 = -1; for (o = eo[i]; o--; ) { int j = ej[i][o]; if (j1 == -1 || cc[j1] < cc[j]) j2 = j1, j1 = j; else if (j2 == -1 || cc[j2] < cc[j]) j2 = j; } for (o = eo[i]; o--; ) { int j = ej[i][o], w = ew[i][o]; if (j != p) { remove_(j); if ((k = jj[j]) != -1) add(k); k = j != j1 ? j1 : j2; cc[i] = cc[k] + w; remove_(k), add(i); dfs2(i, j); remove_(i), add(k); if ((k = jj[j]) != -1) remove_(k); add(j); } } cc[i] = c; } int main() { int h, i, j, w; scanf("%d%d", &n, &k); if (n == 1) { printf("0\n"); return 0; } if (n == 2) { scanf("%*d%*d%d", &w); printf("%d\n", w); return 0; } for (i = 0; i < n; i++) { ej[i] = (int *) malloc(2 * sizeof *ej[i]); ew[i] = (int *) malloc(2 * sizeof *ew[i]); } for (h = 0; h < n - 1; h++) { scanf("%d%d%d", &i, &j, &w), i--, j--; append(i, j, w), append(j, i, w); } i = 0; while (eo[i] == 1) i++; dfs1(-1, i), add(jj[i]); dfs2(-1, i); for (i = 0; i < n; i++) printf("%lld\n", ans[i]); return 0; }

Compilation message (stderr)

Main.c: In function 'append':
Main.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Main.c: In function 'main':
Main.c:150:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:156:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%*d%*d%d", &w);
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:165:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   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...