oj.uz

Submission #173785

# Submission time Handle Problem Language Result Execution time Memory
173785 2020-01-05T12:10:25 Z fedoseevtimofey Beads and wires (APIO14_beads) C++17
0 / 100
 6 ms 5112 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <complex>
#include <functional>
 
using namespace std;
 
typedef long long ll;

const int N = 2e5 + 7;

vector <pair <int, int>> g[N];

int dp[N][2];

void dfs(int u, int p, int wp) {
  int sum = 0;
  vector <int> vals;
  for (auto [v, w] : g[u]) {
    if (v != p) {
      dfs(v, u, w);
      sum += dp[v][1];
      vals.push_back(dp[v][0] + w - dp[v][1]);
    }
  }
  dp[u][0] = sum;
  sort(vals.rbegin(), vals.rend());
  if (vals.size() >= 2) {
    dp[u][0] = max(dp[u][0], sum + vals[0] + vals[1]);
  }
  if (p != -1 && vals.size() >= 1) {
    dp[u][1] = sum + vals[0] + wp;
  }
  dp[u][1] = max(dp[u][1], dp[u][0]);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  for (int i = 0; i + 1 < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dfs(0, -1, 0);
  cout << dp[0][1] << '\n';
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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