#include "roads.h" #include <stdlib.h> #include <vector> using namespace std; typedef vector<int> vi; typedef vector<long long> vl; long long max(long long a, long long b) { return a > b ? a : b; } const int N = 100000; unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } void sort(long long *aa, int l, int r) { while (l < r) { int i = l, j = l, k = r; long long a = aa[l + rand_() % (r - l)], tmp; while (j < k) if (aa[j] == a) j++; else if (aa[j] < a) { tmp = aa[i], aa[i] = aa[j], aa[j] = tmp; i++, j++; } else { k--; tmp = aa[j], aa[j] = aa[k], aa[k] = tmp; } sort(aa, l, i); l = k; } } int ii[N - 1], jj[N - 1], ww[N - 1]; int *eh[N], eo[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 xx[N], dp[N], dq[N]; int k; void dfs(int p, int i) { int o, m, h; long long x; x = 0; for (o = eo[i]; o--; ) { int h = eh[i][o], j = i ^ ii[h] ^ jj[h]; if (j != p) { dfs(i, j); x += dp[j]; } } m = 0; for (o = eo[i]; o--; ) { int h = eh[i][o], j = i ^ ii[h] ^ jj[h]; if (j != p) xx[m++] = dq[j] + ww[h] - dp[j]; } sort(xx, 0, m); dp[i] = x; for (h = m - 1; h >= 0 && h >= m - k && xx[h] > 0; h--) dp[i] += xx[h]; dq[i] = x; for (h = m - 1; h >= 0 && h >= m - (k - 1) && xx[h] > 0; h--) dq[i] += xx[h]; } vl minimum_closure_costs(int n, vi ii_, vi jj_, vi ww_) { vl ans(n); int h, i, star, path; for (h = 0; h < n - 1; h++) ii[h] = ii_[h], jj[h] = jj_[h], ww[h] = ww_[h]; star = 1; for (h = 0; h < n - 1; h++) if (ii[h] != 0) { star = 0; break; } path = 1; for (h = 0; h < n - 1; h++) if (ii[h] != h || jj[h] != h + 1) { path = 0; break; } star = path = 0; if (star) { for (h = 0; h < n - 1; h++) xx[h] = ww[h]; sort(xx, 0, n - 1); for (h = n - 1; h >= 0; h--) ans[h] = h == n - 1 ? 0 : ans[h + 1] + xx[n - 2 - h]; } else if (path) { long long dp, dq, dp_, dq_; for (h = 0; h < n; h++) ans[h] = 0; for (h = 0; h < n - 1; h++) ans[0] += ww[h]; dp = ww[0], dq = 0; for (h = 1; h < n - 1; h++) dp_ = dq + ww[h], dq_ = max(dp, dq), dp = dp_, dq = dq_; ans[1] = ans[0] - max(dp, dq); } else { for (i = 0; i < n; i++) eh[i] = (int *) malloc(2 * sizeof *eh[i]); for (h = 0; h < n - 1; h++) append(ii[h], h), append(jj[h], h); for (h = 0; h < n - 1; h++) ans[0] += ww[h]; for (k = 1; k < n; k++) { dfs(-1, 0); ans[k] = ans[0] - dp[0]; } } return ans; }

roads.cpp: In function 'void append(int, int)':
roads.cpp:47:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   47 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~