Submission #985840

#	Time	Username	Problem	Language	Result	Execution time	Memory
985840		abczz	Beads and wires (APIO14_beads)	C++14	0 / 100	1 ms	2652 KiB

beads

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

ll n, a, b, c, dp[100000][2];
vector <array<ll, 2> > adj[100000];

void dfs(ll u, ll p, ll w) {
  ll res = 0, sz = 0, z = -1e18;
  vector <ll> V;
  for (auto [v, x] : adj[u]) {
    if (v == p) continue;
    dfs(v, u, x);
    res += dp[v][0];
    V.push_back(dp[v][1]+x-dp[v][0]);
  }
  sort(V.begin(), V.end());
  dp[u][0] = max(dp[u][0], res);
  dp[u][1] = max(dp[u][1], res);
  if (!V.empty()) dp[u][0] = max(dp[u][0], res + w + V.back());
  if (V.size() >= 2) {
    dp[u][0] = max(dp[u][0], res + V.back() + V[V.size()-2]);
    dp[u][1] = max(dp[u][1], res + V.back() + V[V.size()-2]);
  }
}
int main() {
  cin >> n;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b >> c;
    --a, --b;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  dfs(0, -1, -1e18);
  cout << max(dp[0][0], dp[0][1]) << '\n';
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int, long long int)':
beads.cpp:15:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |   for (auto [v, x] : adj[u]) {
      |             ^
beads.cpp:13:15: warning: unused variable 'sz' [-Wunused-variable]
   13 |   ll res = 0, sz = 0, z = -1e18;
      |               ^~
beads.cpp:13:23: warning: unused variable 'z' [-Wunused-variable]
   13 |   ll res = 0, sz = 0, z = -1e18;
      |                       ^

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