oj.uz

Submission #966268

# Submission time Handle Problem Language Result Execution time Memory
966268 2024-04-19T15:51:22 Z four_specks Beads and wires (APIO14_beads) C++17
0 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>

using namespace std;

namespace {

template <typename Fun>
struct YCombinator {
  template <typename T>
  YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun(ref(*this), forward<Args>(args)...);
  }

 private:
  Fun fun;
};

template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;

}  // namespace

void solve() {
  int n;
  cin >> n;
  vector<vector<pair<int, long>>> adj(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    long x;
    cin >> u >> v >> x;
    --u;
    --v;
    adj[u].emplace_back(v, x);
    adj[v].emplace_back(u, x);
  }
  vector<array<long, 2>> dp(n);
  YCombinator([&](auto self, int u, int p) -> void {
    vector<pair<int, long>> ch;
    for (auto [v, x] : adj[u]) {
      if (v != p) {
        ch.emplace_back(v, x);
        self(v, u);
      }
    }
    int k = (int)ch.size();
    vector<long> res(k);
    for (int i = 0; i < k; i++) {
      auto [v, x] = ch[i];
      res[i] = dp[v][0];
      if (dp[v][1] != -1) {
        res[i] = max(res[i], dp[v][1] + x);
      }
    }
    vector<long> pref(k + 1), suff(k + 1);
    for (int i = 0; i < k; i++) {
      pref[i + 1] = pref[i] + res[i];
    }
    for (int i = k - 1; i >= 0; i--) {
      suff[i] = suff[i + 1] + res[i];
    }
    dp[u][0] = pref[k];
    dp[u][1] = -1;
    for (int i = 0; i < k; i++) {
      auto [v, x] = ch[i];
      if (dp[u][1] != -1) {
        dp[u][0] = max(dp[u][0], dp[u][1] + suff[i + 1] + dp[v][0] + x);
      }
      if (dp[u][1] != -1) {
        dp[u][1] += res[i];
      }
      dp[u][1] = max(dp[u][1], pref[i] + dp[v][0] + x);
    }
  })(1, -1);
  long ans = dp[1][0];
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();

  return 0;
}

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 1 ms 600 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 1 ms 600 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 1 ms 600 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 1 ms 600 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -