結果
| 問題 | No.1615 Double Down |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-06-21 22:48:54 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 13,517 bytes |
| コンパイル時間 | 1,583 ms |
| コンパイル使用メモリ | 123,360 KB |
| 最終ジャッジ日時 | 2025-01-22 11:03:23 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 TLE * 27 |
ソースコード
// https://atcoder.jp/contests/practice2/submissions/16936680#line 1 "main.cpp"#include <iostream>#include <algorithm>#include <utility>#include <utility>#include <numeric>#include <vector>#include <array>#include <cassert>#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 {public:class iterator {private:int64_t M_position;public:constexpr iterator(int64_t position) noexcept: M_position(position) { }constexpr void operator ++ () noexcept { ++M_position; }constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }constexpr int64_t operator * () const noexcept { return M_position; }};class reverse_iterator {private:int64_t M_position;public:constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }constexpr void operator ++ () noexcept { --M_position; }constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }constexpr int64_t operator * () const noexcept { return M_position; }};private:const iterator M_first, M_last;public:constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }constexpr iterator begin() const noexcept { return M_first; }constexpr iterator end() const noexcept { return M_last; }constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_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 <tuple>#include <cmath>#line 11 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/network_simplex.cpp"#include <stack>#include <set>#include <type_traits>#line 15 "/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 ¤t, 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 18 "main.cpp"using i32 = int32_t;using i64 = int64_t;using u32 = uint32_t;using u64 = uint64_t;constexpr i32 inf32 = (i32(1) << 30) - 1;constexpr i64 inf64 = (i64(1) << 62) - 1;int main() {i32 N, M, K, L, bit[31] = {1};std::cin >> N >> M >> K >> L;network_simplex<i32, i64> net;const auto src = net.add_node((N < M)? N: M);const auto sink = net.add_node((N < M)? -N: -M);const auto row = net.add_nodes(N);const auto column = net.add_nodes(M);net.add_edge(src, sink, 0, N + M, 0);for (auto k: range(0, N)) net.add_edge(src, row[k], 0, 1, 0);for (auto k: range(0, M)) net.add_edge(column[k], sink, 0, 1, 0);for (auto k: range(1, 31)) bit[k] = bit[k-1] << 1;for (auto k: range(0, L)) {i32 i, j, c;std::cin >> i >> j >> c;net.add_edge(row[i-1], column[j-1], 0, 1, -bit[c]);}const auto ans = net.solve();std::cout << -ans.calculate<i64>() << '\n';return 0;}