제출 #259594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259594		EntityIT	구슬과 끈 (APIO14_beads)	C++14	100 / 100	367 ms	44912 KiB

beads

#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], up[v][0] - max(up[u][0], up[u][1]) + parent_edge + w + up[u][0]);
      }
      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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43