Submission #799320

#	Time	Username	Problem	Language	Result	Execution time	Memory
799320		peijar	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	4948 KiB

beads

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 2e5;

int dp[MAXN][2];
vector<pair<int, int>> adj[MAXN];

void solve(int u, int p, int parWeight) {
  int sum = 0;
  for (auto [v, w] : adj[u])
    if (v != p) {
      solve(v, u, w);
      sum += max(dp[v][0], dp[v][1]);
    }
  vector<int> candidats;
  for (auto [v, w] : adj[u])
    if (v != p)
      candidats.push_back(w + dp[v][0] - max(dp[v][0], dp[v][1]));
  sort(candidats.rbegin(), candidats.rend());

  dp[u][0] = sum;
  if (candidats.size() > 1)
    dp[u][0] = max(dp[u][0], sum + candidats[0] + candidats[1]);

  if (candidats.size() > 0 and u)
    dp[u][1] = max(dp[u][1], sum + candidats[0] + parWeight);
  dbg(u + 1, dp[u][0], dp[u][1]);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets;
  cin >> nbSommets;
  for (int i = 1; i < nbSommets; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  solve(0, 0, 0);
  cout << dp[0][0] << endl;
}

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