oj.uz

Submission #799320

# Submission time Handle Problem Language Result Execution time Memory
799320 2023-07-31T12:37:04 Z peijar Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 4948 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 2e5;

int dp[MAXN][2];
vector<pair<int, int>> adj[MAXN];

void solve(int u, int p, int parWeight) {
  int sum = 0;
  for (auto [v, w] : adj[u])
    if (v != p) {
      solve(v, u, w);
      sum += max(dp[v][0], dp[v][1]);
    }
  vector<int> candidats;
  for (auto [v, w] : adj[u])
    if (v != p)
      candidats.push_back(w + dp[v][0] - max(dp[v][0], dp[v][1]));
  sort(candidats.rbegin(), candidats.rend());

  dp[u][0] = sum;
  if (candidats.size() > 1)
    dp[u][0] = max(dp[u][0], sum + candidats[0] + candidats[1]);

  if (candidats.size() > 0 and u)
    dp[u][1] = max(dp[u][1], sum + candidats[0] + parWeight);
  dbg(u + 1, dp[u][0], dp[u][1]);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets;
  cin >> nbSommets;
  for (int i = 1; i < nbSommets; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  solve(0, 0, 0);
  cout << dp[0][0] << endl;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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