Submission #967325

#	Time	Username	Problem	Language	Result	Execution time	Memory
967325		four_specks	Beads and wires (APIO14_beads)	C++17	100 / 100	133 ms	36576 KiB

beads

#include <bits/stdc++.h>

using namespace std;

namespace {

template <typename Fun>
struct YCombinator {
  template <typename T>
  YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun(ref(*this), forward<Args>(args)...);
  }

 private:
  Fun fun;
};

template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;

}  // namespace

void solve() {
  int n;
  cin >> n;
  vector<vector<pair<int, long>>> adj(n);
  long low = -1;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    long x;
    cin >> u >> v >> x;
    --u;
    --v;
    adj[u].emplace_back(v, x);
    adj[v].emplace_back(u, x);
    low -= x;
  }
  // root at a leaf
  int root = -1;
  for (int u = 0; u < n; u++) {
    if ((int)adj[u].size() == 1) {
      root = u;
      break;
    }
  }
  // dp[u][0] = max val such that it is root and no splitting
  // dp[u][1] = max val such that it is root and has splitting
  // dp[u][2] = max val such that it is connected to parent and no splitting
  // dp[u][3] = max val such that it is connected to parent and has splitting
  vector<array<long, 4>> dp(n);
  YCombinator([&](auto self, int u, int p) -> void {
    vector<pair<int, long>> ch;
    for (auto [v, x] : adj[u]) {
      if (v != p) {
        ch.emplace_back(v, x);
        self(v, u);
      }
    }
    int k = (int)ch.size();
    vector<long> com(k);
    for (int i = 0; i < k; i++) {
      auto [v, x] = ch[i];
      com[i] = max(dp[v][0], x + dp[v][2]);
    }
    vector<long> pref(k + 1), suff(k + 1);
    for (int i = 0; i < k; i++) {
      pref[i + 1] = pref[i] + com[i];
    }
    for (int i = k - 1; i >= 0; i--) {
      suff[i] = suff[i + 1] + com[i];
    }
    dp[u][0] = pref[k];
    dp[u][1] = low;
    if (k >= 2) {
      // if split at u, can split in atmost one subtree of u
      array<long, 3> can;
      can.fill(2 * low);
      for (int i = 0; i < k; i++) {
        auto [v, x] = ch[i];
        can[2] = max(can[2] + com[i], max(can[0] + (x + max(dp[v][0], dp[v][1])), can[1] + (x + dp[v][0])));
        can[0] = max(can[0] + com[i], pref[i] + (x + dp[v][0]));
        can[1] = max(can[1] + com[i], pref[i] + (x + dp[v][1]));
      }
      dp[u][1] = max(dp[u][1], can[2]);
    }
    for (int i = 0; i < k; i++) {
      auto [v, x] = ch[i];
      dp[u][1] = max(dp[u][1], pref[i] + max(dp[v][1], x + dp[v][3]) + suff[i + 1]);
    }
    dp[u][2] = low;
    for (int i = 0; i < k; i++) {
      auto [v, x] = ch[i];
      dp[u][2] = max(dp[u][2], pref[i] + (x + dp[v][0]) + suff[i + 1]);
    }
    dp[u][3] = low;
    for (int i = 0; i < k; i++) {
      auto [v, x] = ch[i];
      dp[u][3] = max(dp[u][3], pref[i] + (x + dp[v][1]) + suff[i + 1]);
    }
  })(root, -1);
  long ans = max(dp[root][0], dp[root][1]);
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();

  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43