結果

問題 No.417 チューリップバブル
ユーザー hydrogen
提出日時 2019-09-13 00:00:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 464 ms / 2,000 ms
コード長 4,373 bytes
コンパイル時間 1,479 ms
コンパイル使用メモリ 117,460 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-02 17:18:59
合計ジャッジ時間 7,634 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define FOR(i,a,b) for (int i=(a),for_##i##_max=(b);i<=(for_##i##_max);++i)
#define RFOR(i,a,b) for (int i=(a),rfor_##i##_min=(b);i>=(rfor_##i##_min);--i)
#define REP(i,n) for (int i=0,rep_##i##_len=(n);i<(rep_##i##_len);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)
namespace { // Basics
template<typename T>
void chmin(T &x, T y) {
  x = std::min(x, y);
}
template<typename T>
void chmax(T &x, T y) {
  x = std::max(x, y);
}
template<typename T>
__attribute__((unused))
const auto minimum = static_cast<T const &(*)(T const &, T const &)>(std::min);
template<typename T>
__attribute__((unused))
const auto maximum = static_cast<T const &(*)(T const &, T const &)>(std::max);
template<typename T>
int cmp3(T lhs, T rhs) { return (lhs == rhs) ? 0 : (lhs > rhs) ? 1 : -1; }
template<typename T>
__attribute__((unused))
T constexpr infty = std::numeric_limits<T>::max / 3;
template<>
__attribute__((unused))
auto constexpr infty<int> = 1'100'100'100;
template<>
__attribute__((unused))
auto constexpr infty<long long int> = 100'500'400'300'200'100LL;
using lli = long long int;
using ld = long double;
} // namespace
namespace { // Graph Basics
template<typename WeightT>
struct edge {
  int from, to;
  WeightT weight;
  edge(int s, int d, WeightT w): from(s), to(d), weight(w) {}
};
template<typename WeightT>
bool
operator< (edge<WeightT> const &lhs, edge<WeightT> const &rhs) {
  if (lhs.weight != rhs.weight) {
    return lhs.weight < rhs.weight;
  } else if (lhs.from != rhs.from) {
    return lhs.from < rhs.from;
  }
  return lhs.to < rhs.to;
}
template<typename WeightT>
using edges = std::vector<edge<WeightT> >;
template<typename WeightT>
using adjacency_list = std::vector<edges<WeightT> >;
template<typename WeightT>
void
add_undir_edge(adjacency_list<WeightT> &G, int u, int v, WeightT w) {
  G[u].emplace_back(u, v, w);
  G[v].emplace_back(v, u, w);
}
template<typename WeightT>
adjacency_list<WeightT>
inverse_graph(adjacency_list<WeightT> const &G) {
  size_t const n = G.size();
  adjacency_list<WeightT> F(n);
  for (auto &&es: G) for (auto &&e: es) {
    F[e.to].emplace_back(e.to, e.from, e.weight);
  }
  return F;
}
template <typename WeightT>
edges<WeightT>
all_edges(adjacency_list<WeightT> const &G) {
  auto const E = std::accumulate(begin(G), end(G), 0,
      [](auto x, auto vec) { return x + vec.size(); });
  edges<WeightT> es;
  es.reserve(E);
  for (auto &&vec: G) {
    std::copy(begin(vec), end(vec), std::back_inserter(es));
  }
  return es;
}
} // namespace
namespace { // rooted_tree
template <typename WeightT>
struct rooted_tree {
  size_t size;
  std::vector<size_t> topo;
  std::vector<size_t> par;
  std::vector<edges<WeightT>> children;
};
template <typename WeightT>
rooted_tree<WeightT> make_rooted_tree(adjacency_list<WeightT> const &G, size_t root) {
  size_t N = G.size();
  std::vector<size_t> topo, par(N);
  par[root] = N + 1;
  std::vector<edges<WeightT>> ch(N);
  std::vector<bool> used(N, false);
  std::stack<size_t> stk;
  stk.push(root); used[root] = true;
  while (!stk.empty()) {
    size_t const u = stk.top(); stk.pop();
    topo.push_back(u);
    for (auto &&e : G[u]) {
      if (used[e.to]) { continue; }
      stk.push(e.to); used[e.to] = true;
      par[e.to] = u;
      ch[u].push_back(e);
    }
  }
  return { N, topo, par, ch };
}
} // namespace
using namespace std;
using Graph = adjacency_list<lli>;
void solve(int N, int M, vector<lli> Us, Graph const &G) {
  auto const tree = make_rooted_tree(G, 0);
  vector<vector<lli>> dp(N, vector<lli>(M+1, 0));
  REP(u, N) FOR(t, 0, M) { dp[u][t] = Us[u]; }
  RREP(i, N) {
    int u = tree.topo[i];
    for (auto &&e : tree.children[u]) {
      RFOR(t, M, 2*e.weight) FOR(s, 0, t-2*e.weight) {
        chmax(dp[u][t], dp[u][s]+dp[e.to][t-s-2*e.weight]);
      }
    }
  }
  cout << dp[0][M] << endl;
}
int main() {
  int N, M; cin >> N >> M;
  Graph G(N);
  vector<lli> Us;
  REP(i, N) {
    lli U; cin >> U;
    Us.push_back(U);
  }
  REP(i, N-1) {
    lli A, B, C; cin >> A >> B >> C;
    add_undir_edge(G, A, B, C);
  }
  solve(N, M, Us, G);
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0