Submission #239746

#	Time	Username	Problem	Language	Result	Execution time	Memory
239746		neihcr7j	Beads and wires (APIO14_beads)	C++14	100 / 100	193 ms	22636 KiB

beads

#include<bits/stdc++.h>

#define oo 1000000000
#define maxn 200005

using namespace std;
typedef long long ll;

int n;

vector < pair < int, int > > g[maxn];

int dp[maxn][4];

void dfs(int u, int du) {
  dp[u][0] = dp[u][1] = 0;
  dp[u][2] = dp[u][3] = -oo;

  for (auto i : g[u]) {
    int v = i.first, w = i.second;
    if (du == v) continue;

    dfs(v, u);

    int a = max(dp[u][0] + max(dp[v][1], dp[v][2] + w), dp[u][1] + dp[v][3] + w);

    a = max(a, max(dp[u][2] + max(dp[v][0], dp[v][1]), dp[u][3] + dp[v][1]) + w);
    a = max(a, dp[u][1] + max(dp[v][0], dp[v][1]));

    int b = dp[u][1] + max(dp[v][1], dp[v][2] + w);
    int c = max(dp[u][2] + max(dp[v][2] + w, dp[v][1]), dp[u][1] + dp[v][1] + w);
    int d = max(dp[u][3] + max(dp[v][2] + w, dp[v][1]), dp[u][1] + max(dp[v][0], dp[v][1]) + w);

    dp[u][0] = a;
    dp[u][1] = b;
    dp[u][2] = c;
    dp[u][3] = d;

    //if (u == 1) cerr << a << ' ' << b << ' ' << c <<  ' ' << d << '\n';
  }
}

int main(){
  #define TASK "ABC"
  //freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n;

  for (int i = 1; i < n; ++i) {
    int u, v, c;
    cin >> u >> v >> c;

    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }

  int root = 1;
  dfs(root, root);

  //cerr << dp[8][1] << '\n';

  cout << max(dp[root][0], dp[root][1]);

  return 0;
}

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