oj.uz

Submission #259558

# Submission time Handle Problem Language Result Execution time Memory
259558 2020-08-08T02:31:14 Z EntityIT Beads and wires (APIO14_beads) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

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

  int n_vertices; cin >> n_vertices;
  vec<pair<int, int>, 2> edges_vertices(n_vertices);
  for (int i = 1; i < n_vertices; ++i) {
    int u, v, w; cin >> u >> v >> w; --u; --v;
    edges_vertices[u].emplace_back(v, w);
    edges_vertices[v].emplace_back(u, w);
  }

  vec<int, 2> down(n_vertices, 2);
  vec<array<int, 2>, 1> max_changes_vertices(n_vertices);
  function<void(int, int, int)> Down = [&](int u, int parent, int parent_edge) {
    max_changes_vertices[u][0] = max_changes_vertices[u][1] = numeric_limits<int>::min();
    for (auto& edge : edges_vertices[u]) {
      int v, w; tie(v, w) = edge;
      if (v == parent) {
        continue;
      }
      Down(v, u, w);
      down[u][0] += max(down[v][0], down[v][1]);
      int change = - max(down[v][0], down[v][1]) + w + down[v][0];
      for (int i = 0; i < SZ(max_changes_vertices[u]); ++i) {
        if (change > max_changes_vertices[u][i]) {
          swap(change, max_changes_vertices[u][i]);
        }
      }
    }
    down[u][1] = max_changes_vertices[u][0] != numeric_limits<int>::min() && parent_edge != numeric_limits<int>::min() ? down[u][0] + max_changes_vertices[u][0] + parent_edge : numeric_limits<int>::min();
  };
  Down(0, -1, numeric_limits<int>::min());

  vec<int, 2> up(n_vertices, 2);
  up[0][1] = numeric_limits<int>::min();
  function<void(int, int, int)> Up = [&](int u, int parent, int parent_edge) {
    for (auto& edge : edges_vertices[u]) {
      int v, w; tie(v, w) = edge;
      if (v == parent) {
        continue;
      }

      up[v][0] = max(up[u][0], up[u][1]) + down[u][0] - max(down[v][0], down[v][1]);
      up[v][1] = numeric_limits<int>::min();
      if (parent_edge != numeric_limits<int>::min()) {
        Maximize(up[v][1], w + parent_edge + down[u][0] - max(down[v][0], down[v][1]));
      }
      int change = - max(down[v][0], down[v][1]) + w + down[v][0];
      if (max_changes_vertices[u][0] == change) {
        if (max_changes_vertices[u][1] != numeric_limits<int>::min()) {
          Maximize(up[v][1], up[v][0] + max_changes_vertices[u][1] + w);
        }
      } else {
        if (max_changes_vertices[u][0] != numeric_limits<int>::min()) {
          Maximize(up[v][1], up[v][0] + max_changes_vertices[u][0] + w);
        }
      }

      Up(v, u, w);
    }
  };
  Up(0, -1, numeric_limits<int>::min());

  int answer = 0;
  for (int u = 0; u < n_vertices; ++u) {
    Maximize(answer, down[u][0] + max(up[u][0], up[u][1]));
    if (down[u][1] != numeric_limits<int>::min()) {
      Maximize(answer, down[u][1] + up[u][0]);
    }
  }

  cout << answer << '\n';

  return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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