oj.uz

Submission #971221

# Submission time Handle Problem Language Result Execution time Memory
971221 2024-04-28T07:49:47 Z kilkuwu Beads and wires (APIO14_beads) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

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

  int N;
  std::cin >> N;
  std::vector<std::vector<std::pair<int, int>>> adj(N);

  for (int i = 0; i + 1 < N; i++) {
    int u, v, c;
    std::cin >> u >> v >> c;
    --u, --v;
    adj[u].emplace_back(v, c);
    adj[v].emplace_back(u, c);
  }

  std::vector<std::array<int, 2>> dp(N);
  std::vector<int> up(N);

  auto dfs = [&](auto self, int u, int p) -> void { // w is cost go up
    dp[u][0] = dp[u][1] = 0;
    std::vector<int> child;
    for (auto [v, c] : adj[u]) {
      if (v == p) continue;
      child.push_back(v);
      up[v] = c;
      self(self, v, u);
      dp[u][0] += dp[v][1]; // there's an available edge
      dp[u][1] += dp[v][1];
    }

    if (child.empty()) {
      return;
    }

    if (child.size() == 1) {
      if (u != p) {
        dp[u][1] = std::max(dp[u][1], up[u] + up[child[0]] + dp[child[0]][0]);
      }
      return;
    }

    auto get_val = [&](int i) {
      return dp[i][0] - dp[i][1] + up[i];
    };

    std::sort(child.begin(), child.end(), [&](int i, int j) {
      return get_val(i) > get_val(j);
    });

    // take two biggest
    int sum_unused = dp[u][0];
    int cand = sum_unused + get_val(child[0]) + get_val(child[1]);
    dp[u][0] = std::max(dp[u][0], cand);
    dp[u][1] = dp[u][0];


    if (u != p) {
      for (int i : child) {
        dp[u][1] = std::max(dp[u][1], up[u] + get_val(i) + sum_unused);
      }
    }

    dbg(u, dp[u][1], dp[u][0]);
  };

  dfs(dfs, 0, 0);

  std::cout << dp[0][0] << nl;
}

/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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