Submission #1032889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032889		vjudge1	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	6748 KiB

beads

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

#define int long long

const int N = 2e5+5, inf = LLONG_MAX;

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

void dfs(int x, int p, int w) {
  int sum1 = 0;
  int mx = -inf;
  int smx = -inf;
  for (auto& [y, z] : adj[x]) {
    if (y == p) continue;
    dfs(y, x, z);

    sum1 += dp[1][y];

    int nw = dp[0][y] + z - dp[1][y];
    if (nw >= mx) {
      smx = mx;
      mx = nw;
    }
    else if (nw > smx) {
      smx = nw;
    }
  }

  // no activo a nadie
  dp[0][x] = dp[1][x] = sum1;

  // activo a mi padre y a un hijo
  if (mx > -inf) dp[1][x] = max(dp[1][x], sum1 + mx + w);

  // activo a dos hijos
  if (smx > -inf) {
    dp[0][x] = max(dp[0][x], sum1 + mx + smx);
    dp[1][x] = max(dp[1][x], sum1 + mx + smx);
  }
}

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

  cin >> n;
  for (int i = 0; i < n-1; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x--; y--;

    adj[x].push_back(make_pair(y, z));
    adj[y].push_back(make_pair(x, z));
  }

  int ans = inf;
  for (int i = 0; i < n; i++) {
    dfs(i, i, 0);
    ans = min(ans, dp[0][i]);
  }
  cout << ans << "\n";
}

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