#579935 (C++17) No.1288 yuki collection

提出ソース

結果

問題	No.1288 yuki collection
ユーザー	KoD
提出日時	2020-11-14 00:31:23
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	480 ms / 5,000 ms
コード長	13,674 bytes
コンパイル時間	1,824 ms
コンパイル使用メモリ	129,628 KB
実行使用メモリ	4,492 KB
最終ジャッジ日時	2023-09-30 04:30:42
合計ジャッジ時間	6,733 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	83 ms 4,376 KB
testcase_14	AC	74 ms 4,376 KB
testcase_15	AC	69 ms 4,376 KB
testcase_16	AC	67 ms 4,380 KB
testcase_17	AC	80 ms 4,376 KB
testcase_18	AC	68 ms 4,376 KB
testcase_19	AC	86 ms 4,480 KB
testcase_20	AC	91 ms 4,380 KB
testcase_21	AC	404 ms 4,380 KB
testcase_22	AC	480 ms 4,380 KB
testcase_23	AC	373 ms 4,380 KB
testcase_24	AC	84 ms 4,376 KB
testcase_25	AC	75 ms 4,380 KB
testcase_26	AC	81 ms 4,492 KB
testcase_27	AC	58 ms 4,376 KB
testcase_28	AC	63 ms 4,380 KB
testcase_29	AC	50 ms 4,376 KB
testcase_30	AC	18 ms 4,380 KB
testcase_31	AC	36 ms 4,380 KB
testcase_32	AC	30 ms 4,384 KB
testcase_33	AC	145 ms 4,380 KB
testcase_34	AC	85 ms 4,376 KB
testcase_35	AC	103 ms 4,380 KB
testcase_36	AC	62 ms 4,376 KB
testcase_37	AC	74 ms 4,380 KB
testcase_38	AC	284 ms 4,376 KB
testcase_39	AC	106 ms 4,380 KB
testcase_40	AC	8 ms 4,380 KB
testcase_41	AC	2 ms 4,376 KB
testcase_42	AC	2 ms 4,380 KB

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

ソースコード

raw source code

#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <map>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/chmin_chmax.cpp"

template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { lhs = rhs; return true; }
  return false;
}

template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { lhs = rhs; return true; }
  return false;
}

/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/rev.cpp"

#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/cpp_programming/Library/other/rev.cpp"

template <class T>
class rev_impl {
public:
  using iterator = decltype(std::rbegin(std::declval<T>()));

private:
  const iterator M_begin;
  const iterator M_end;

public:
  constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
  constexpr iterator begin() const noexcept { return M_begin; }
  constexpr iterator end() const noexcept { return M_end; }
};

template <class T>
constexpr decltype(auto) rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}

/**
 * @title Reverser
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/adjust_index.cpp"

#include <cstddef>
#line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/other/adjust_index.cpp"

class adjust_index {
private:
  const size_t M_stuff, M_size;

public:
  explicit adjust_index(const size_t stuff, const size_t size): 
    M_stuff(stuff), M_size(size) 
  { }

  size_t operator [] (const size_t index) const {
    assert(index < M_size);
    return M_stuff + index;
  }
  size_t to_index(const size_t fixed) const {
    assert(fixed >= M_stuff);
    assert(fixed < M_size + M_stuff);
    return fixed - M_stuff;
  }
  size_t size() const {
    return M_size;
  }
};

/**
 * @title Index Adjustment
 */
#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"

#line 6 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"
#include <cstdint>
#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"
#include <cmath>
#line 10 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"
#include <stack>
#include <set>
#include <type_traits>
#line 14 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"

template <class Flow, class Cost>
class network_simplex {
public:
  using flow_type = Flow;
  using cost_type = Cost;
  using size_type = size_t;
  using node_id   = size_t;
  using edge_id   = size_t;

  static_assert(std::is_signed<flow_type>::value, "flow-type must be signed integer");
  static_assert(std::is_integral<flow_type>::value, "flow-type must be signed integer");
  static_assert(std::is_signed<cost_type>::value, "cost-type must be signed integer");
  static_assert(std::is_integral<cost_type>::value, "cost-type must be signed integer");

  struct return_type {
  public:
    const bool feasible;
    const std::vector<cost_type> potentials;
    const std::vector<std::pair<flow_type, cost_type>> edges;

    explicit return_type(
      const bool feasible,
      const std::vector<cost_type> potentials,
      const std::vector<std::pair<flow_type, cost_type>> edges
    ): feasible(feasible), potentials(potentials), edges(edges) { }

    template <class T>
    T calculate() const {
      T res = 0;
      for (const auto &e: edges) {
        res += (T) e.first * e.second;
      }
      return res;
    }
  };

private:
  class edge_type {
  public:
    const node_id src, dst;
    flow_type flow;
    const flow_type capacity;
    const cost_type cost;

    explicit edge_type(
      const node_id src, const node_id dst,
      const flow_type flow, const flow_type capacity,
      const cost_type cost
    ): src(src), dst(dst), flow(flow), capacity(capacity), cost(cost) { }
  };

  class node_type {
  public:
    flow_type balance;
    cost_type potential;
    std::set<edge_id> tree_edges;
    size_type depth;
    edge_id parent_edge;

    explicit node_type(const flow_type balance = 0):
      balance(balance), potential(0), tree_edges(), depth(0), parent_edge(-1)
    { }
  };

  std::vector<edge_type> edges;
  std::vector<node_type> nodes;

  static edge_id rev_id(const edge_id eid) {
    return (eid ^ 1);
  }
  template <class T>
  static bool minimize(T &current, const T &new_cost) {
    if (current > new_cost) { current = new_cost; return true; }
    return false;
  }

  flow_type residual_capacity(const edge_id eid) const {
    return edges[eid].capacity - edges[eid].flow;
  }
  cost_type reduced_cost(const edge_id eid) const {
    return edges[eid].cost + nodes[edges[eid].src].potential - nodes[edges[eid].dst].potential;
  }
  bool send_flow(const edge_id eid, const flow_type flow) {
    edges[eid].flow += flow;
    edges[rev_id(eid)].flow -= flow;
    return edges[eid].flow == edges[eid].capacity;
  }

  void precompute() {
    cost_type inf_cost = 1;
    for (const auto &e: edges) {
      if (e.cost > 0) inf_cost += e.cost;
    }
    const auto root = add_node();
    for (node_id nid = 0; nid != root; ++nid) {
      const auto flow = nodes[nid].balance;
      if (flow < 0) {
        const auto eid = add_edge(root, nid, (flow_type) 0, -flow, inf_cost) << 1;
        send_flow(eid, -flow);
        nodes[root].tree_edges.insert(eid);
        nodes[nid].tree_edges.insert(rev_id(eid));
      }
      else {
        const auto eid = add_edge(nid, root, (flow_type) 0, flow + 1, inf_cost) << 1;
        send_flow(eid, flow);
        nodes[nid].tree_edges.insert(eid);
        nodes[root].tree_edges.insert(rev_id(eid));
      }
    }
    evert(root);
  }

  void evert(const node_id root) {
    std::stack<node_id> stack;
    stack.push(root);
    while (!stack.empty()) {
      const auto nid = stack.top();
      stack.pop();
      for (const auto eid: nodes[nid].tree_edges) {
        if (eid != nodes[nid].parent_edge) {
          const auto dst = edges[eid].dst;
          nodes[dst].potential = nodes[nid].potential + edges[eid].cost;
          nodes[dst].depth = nodes[nid].depth + 1;
          nodes[dst].parent_edge = rev_id(eid);
          stack.push(dst);
        }
      }
    }
  }

  edge_id select_edge() {
    static const size_type block_size = (size_type) std::sqrt(edges.size());
    static size_type edge_scan = 0;
    static const auto advance = [&] {
      if (++edge_scan == edges.size()) edge_scan = 0;
    };
    size_type step = 0;
    while (step < edges.size()) {
      cost_type optimal_cost = 0;
      edge_id select = -1;
      for (size_type minor = 0; minor != block_size; ++minor) {
        if (step == edges.size()) break;
        const edge_id eid = edge_scan;
        advance();
        ++step;
        if (residual_capacity(eid) > 0) {
          if (minimize(optimal_cost, reduced_cost(eid))) select = eid;
        }
      }
      if (~select) return select;
    }
    return (edge_id) -1;
  }

  void pivot(const edge_id eid) {
    flow_type send = residual_capacity(eid);
    auto src_side = edges[eid].src;
    auto dst_side = edges[eid].dst;
    while (src_side != dst_side) {
      if (nodes[src_side].depth > nodes[dst_side].depth) {
        const auto down_edge = rev_id(nodes[src_side].parent_edge);
        minimize(send, residual_capacity(down_edge));
        src_side = edges[down_edge].src;
      }
      else {
        const auto up_edge = nodes[dst_side].parent_edge;
        minimize(send, residual_capacity(up_edge));
        dst_side = edges[up_edge].dst;
      }
    }
    const auto lca = src_side;
    edge_id remove = -1;
    enum leaving_arc { SRC, DST, ENT };
    leaving_arc state = ENT;
    src_side = edges[eid].src;
    while (src_side != lca) {
      const auto down_edge = rev_id(nodes[src_side].parent_edge);
      if (send_flow(down_edge, send)) {
        if (~remove == 0) {
          remove = down_edge;
          state = SRC;
        }
      }
      src_side = edges[down_edge].src;
    }
    if (send_flow(eid, send)) {
      remove = eid;
      state = ENT;
    }
    dst_side = edges[eid].dst;
    while (dst_side != lca) {
      const auto up_edge = nodes[dst_side].parent_edge;
      if (send_flow(up_edge, send)) {
        remove = up_edge;
        state = DST;
      }
      dst_side = edges[up_edge].dst;
    }
    if (state == ENT) return;
    nodes[edges[eid].src].tree_edges.insert(eid);
    nodes[edges[eid].dst].tree_edges.insert(rev_id(eid));
    nodes[edges[remove].src].tree_edges.erase(remove);
    nodes[edges[remove].dst].tree_edges.erase(rev_id(remove));
    evert(state == SRC ? edges[eid].dst : edges[eid].src);
  }

public:
  explicit network_simplex() = default;
  explicit network_simplex(const size_type size) {
    add_nodes(size);
  }

  node_id add_node(const flow_type balance = 0) {
    const node_id res = nodes.size();
    nodes.emplace_back(balance);
    return res;
  }
  adjust_index add_nodes(const size_type size) {
    const size_type cur = nodes.size();
    nodes.resize(cur + size);
    return adjust_index(cur, size);
  }

  void add_supply(const node_id node, const flow_type supply) {
    assert(node < nodes.size());
    nodes[node].balance += supply;
  }
  void add_demand(const node_id node, const flow_type demand) {
    assert(node < nodes.size());
    nodes[node].balance -= demand;
  }
   
  edge_id add_edge(
    const node_id src, const node_id dst, 
    const flow_type lower_bound, const flow_type upper_bound,
    const cost_type cost
  ) {
    assert(src < nodes.size());
    assert(dst < nodes.size());
    assert(lower_bound <= upper_bound);
    const edge_id res = edges.size() >> 1;
    edges.emplace_back(src, dst, lower_bound, upper_bound, cost);
    edges.emplace_back(dst, src, -lower_bound, -lower_bound, -cost);
    if (lower_bound != (flow_type) 0) {
      add_demand(src, lower_bound);
      add_supply(dst, lower_bound);
    }
    return res;
  }

  return_type solve() {
    precompute();
    edge_id select = select_edge();
    while (~select) {
      pivot(select);
      select = select_edge();
    }
    bool feasible = true;
    const auto split = edges.size() - 2 * (nodes.size() - 1);
    for (edge_id eid = split; eid != edges.size(); ++eid) {
      if (edges[eid].flow > 0) {
        feasible = false;
        break;
      }
    }
    std::vector<cost_type> pt(nodes.size() - 1);
    for (node_id nid = 0; nid != nodes.size() - 1; ++nid) {
      pt[nid] = nodes[nid].potential;
    }
    std::vector<std::pair<flow_type, cost_type>> es;
    es.reserve(split >> 1);
    for (edge_id eid = 0; eid != split; eid += 2) {
      es.emplace_back(edges[eid].flow, edges[eid].cost);
    }
    return return_type(feasible, pt, es);
  }

};

/**
 * @title Network Simplex
 */
#line 19 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

int main() {
  usize N;
  std::cin >> N;
  std::string S;
  std::cin >> S;
  std::vector<i64> V(N);
  for (auto &x: V) {
    std::cin >> x;
  }
  std::vector<usize> C(N);
  for (auto i: range(0, N)) {
    if (S[i] == 'y') {
      C[i] = 0;
    }
    if (S[i] == 'u') {
      C[i] = 1;
    }
    if (S[i] == 'k') {
      C[i] = 2;
    }
    if (S[i] == 'i') {
      C[i] = 3;
    }
  }
  network_simplex<i64, i64> net;
  const auto inf = (i64) N;
  const auto src = net.add_node(inf);
  const auto sink = net.add_node(-inf);
  const auto index = net.add_nodes(N);
  net.add_edge(src, sink, 0, inf, 0);
  std::array<usize, 4> right;
  right.fill(N);
  for (auto i: rev(range(0, N))) {
    if (right[C[i]] != N) {
      net.add_edge(index[i], index[right[C[i]]], 0, inf, 0);
    }
    if (C[i] == 0) {
      net.add_edge(src, index[i], 0, 1, 0);
    }
    if (C[i] == 3) {
      net.add_edge(index[i], sink, 0, 1, -V[i]);
    }
    else {
      const auto to = right[C[i] + 1];
      if (to != N) {
        net.add_edge(index[i], index[to], 0, 1, -V[i]);
      }
    }
    right[C[i]] = i;
  }
  std::cout << -net.solve().calculate<i64>() << '\n';
  return 0;
}

yukicoder

結果

テストケース

ソースコード