結果
| 問題 | No.1615 Double Down |
| ユーザー |
 ygussany
|
| 提出日時 | 2021-06-21 22:48:54 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 13,517 bytes |
| コンパイル時間 | 1,626 ms |
| コンパイル使用メモリ | 128,644 KB |
| 実行使用メモリ | 22,896 KB |
| 最終ジャッジ日時 | 2024-07-17 15:17:46 |
| 合計ジャッジ時間 | 24,540 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
ソースコード
// 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;
}