Submission #587247

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

beads

/**
 *    author:  wxhtzdy
 *    created: 01.07.2022 14:47:42
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u; --v;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);  
  }
  vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(2, vector<long long>(2)));   
  function<void(int, int, int)> Dfs = [&](int v, int pr, int up) {
    vector<long long> f, q;
    long long ft = 0, dw = 0;
    for (auto& p : g[v]) {
      int u = p.first;
      int w = p.second;
      if (u == pr) {
        continue;
      }
      Dfs(u, v, w);
      ft += max(dp[u][0][1], dp[u][1][1]);
      dw += max({dp[u][0][0], dp[u][0][1], dp[u][1][1]});
      f.push_back(w + max(dp[u][0][0], dp[u][0][1]) - max(dp[u][0][1], dp[u][1][1]));
      q.push_back(w + max(dp[u][0][0], dp[u][0][1]) - max({dp[u][0][0], dp[u][0][1], dp[u][1][1]})); 
    }
    dp[v][0][1] = ft;
    dp[v][0][0] = dw;           
    sort(f.rbegin(), f.rend()); 
    sort(q.rbegin(), q.rend());
    if ((int) f.size() >= 2) {
      dp[v][0][0] = max(dw, ft + f[0] + f[1]);
    }
    if ((int) f.size() >= 1) {
      dp[v][1][1] = ft + up + f[0];
    }                                           
  };
  long long ans = 0;
  for (int root = 0; root < n; root++) {
    for (int i = 0; i < n; i++) {
      for (int p = 0; p < 2; p++) {
        for (int q = 0; q < 2; q++) {
          dp[i][p][q] = 0;
        }
      }
    }
    Dfs(root, root, -1e9);
    ans = max(dp[root][0][0], dp[root][0][1]);
    for (int i = 0; i < n; i++) {
      if (root == i) {
        continue;
      }
      for (int p = 0; p < 2; p++) {
        for (int q = 0; q < 2; q++) {
          ans = max(ans, dp[i][p][q]);
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

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