oj.uz

Submission #587183

# Submission time Handle Problem Language Result Execution time Memory
587183 2022-07-01T12:57:33 Z MilosMilutinovic Beads and wires (APIO14_beads) C++14
0 / 100
 1 ms 320 KB 
/**
 *    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<long long>> dp(n, vector<long long>(2));   
  function<void(int, int, int)> Dfs = [&](int v, int pr, int up) {
    vector<long long> f;
    long long ft = 0;
    for (auto& p : g[v]) {
      int u = p.first;
      int w = p.second;
      if (u == pr) {
        continue;
      }
      Dfs(u, v, w);                                  
      ft += dp[u][1];
      f.push_back(w + dp[u][0] - dp[u][1]); 
    }
    dp[v][0] = ft;            
    for (int it = 0; it < 2; it++) {
      sort(f.rbegin(), f.rend());
      long long s = 0;
      for (int i = 0; i + 1 < (int) f.size() && i < 2; i += 2) {
        s += f[i] + f[i + 1];
        dp[v][it] = max(dp[v][it], ft + s);
      }
      f.push_back(up);
    }
    dp[v][1] = max(dp[v][1], dp[v][0]);
  };
  Dfs(0, 0, 0);
  cout << dp[0][0] << '\n';
  return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -