#378450 (C++14) No.417 チューリップバブル

提出ソース

結果

問題	No.417 チューリップバブル
ユーザー	hydrogen
提出日時	2019-09-13 00:00:12
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	6 ms 6,944 KB
testcase_09	AC	12 ms 6,940 KB
testcase_10	AC	17 ms 6,940 KB
testcase_11	AC	69 ms 6,944 KB
testcase_12	AC	67 ms 6,940 KB
testcase_13	AC	26 ms 6,940 KB
testcase_14	AC	109 ms 6,940 KB
testcase_15	AC	9 ms 6,940 KB
testcase_16	AC	9 ms 6,944 KB
testcase_17	AC	59 ms 6,940 KB
testcase_18	AC	58 ms 6,940 KB
testcase_19	AC	59 ms 6,944 KB
testcase_20	AC	225 ms 6,940 KB
testcase_21	AC	223 ms 6,940 KB
testcase_22	AC	224 ms 6,940 KB
testcase_23	AC	225 ms 6,944 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	225 ms 6,944 KB
testcase_26	AC	21 ms 6,944 KB
testcase_27	AC	156 ms 6,940 KB
testcase_28	AC	226 ms 6,940 KB
testcase_29	AC	222 ms 6,944 KB
testcase_30	AC	223 ms 6,944 KB
testcase_31	AC	222 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	8 ms 6,944 KB
testcase_34	AC	47 ms 6,940 KB
testcase_35	AC	457 ms 6,940 KB
testcase_36	AC	455 ms 6,944 KB
testcase_37	AC	460 ms 6,940 KB
testcase_38	AC	464 ms 6,940 KB
testcase_39	AC	461 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード