Submission #971221

#	Time	Username	Problem	Language	Result	Execution time	Memory
971221		kilkuwu	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	348 KiB

beads

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N;
  std::cin >> N;
  std::vector<std::vector<std::pair<int, int>>> adj(N);

  for (int i = 0; i + 1 < N; i++) {
    int u, v, c;
    std::cin >> u >> v >> c;
    --u, --v;
    adj[u].emplace_back(v, c);
    adj[v].emplace_back(u, c);
  }

  std::vector<std::array<int, 2>> dp(N);
  std::vector<int> up(N);

  auto dfs = [&](auto self, int u, int p) -> void { // w is cost go up
    dp[u][0] = dp[u][1] = 0;
    std::vector<int> child;
    for (auto [v, c] : adj[u]) {
      if (v == p) continue;
      child.push_back(v);
      up[v] = c;
      self(self, v, u);
      dp[u][0] += dp[v][1]; // there's an available edge
      dp[u][1] += dp[v][1];
    }

    if (child.empty()) {
      return;
    }

    if (child.size() == 1) {
      if (u != p) {
        dp[u][1] = std::max(dp[u][1], up[u] + up[child[0]] + dp[child[0]][0]);
      }
      return;
    }

    auto get_val = [&](int i) {
      return dp[i][0] - dp[i][1] + up[i];
    };

    std::sort(child.begin(), child.end(), [&](int i, int j) {
      return get_val(i) > get_val(j);
    });

    // take two biggest
    int sum_unused = dp[u][0];
    int cand = sum_unused + get_val(child[0]) + get_val(child[1]);
    dp[u][0] = std::max(dp[u][0], cand);
    dp[u][1] = dp[u][0];


    if (u != p) {
      for (int i : child) {
        dp[u][1] = std::max(dp[u][1], up[u] + get_val(i) + sum_unused);
      }
    }

    dbg(u, dp[u][1], dp[u][0]);
  };

  dfs(dfs, 0, 0);

  std::cout << dp[0][0] << nl;
}

/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

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