結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー | Kude |
提出日時 | 2021-01-15 23:50:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 865 ms / 2,000 ms |
コード長 | 9,570 bytes |
コンパイル時間 | 2,642 ms |
コンパイル使用メモリ | 232,124 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-11-26 18:42:51 |
合計ジャッジ時間 | 9,462 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 5 ms
5,248 KB |
testcase_07 | AC | 445 ms
6,440 KB |
testcase_08 | AC | 6 ms
5,924 KB |
testcase_09 | AC | 277 ms
6,440 KB |
testcase_10 | AC | 409 ms
6,944 KB |
testcase_11 | AC | 413 ms
6,820 KB |
testcase_12 | AC | 368 ms
6,816 KB |
testcase_13 | AC | 604 ms
6,816 KB |
testcase_14 | AC | 767 ms
6,688 KB |
testcase_15 | AC | 847 ms
6,820 KB |
testcase_16 | AC | 848 ms
6,820 KB |
testcase_17 | AC | 865 ms
6,816 KB |
testcase_18 | AC | 303 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h> #include <algorithm> #include <cassert> #include <limits> #include <queue> #include <vector> #include <algorithm> #include <utility> #include <vector> namespace atcoder { namespace internal { template <class E> struct csr { std::vector<int> start; std::vector<E> elist; csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) { for (auto e : edges) { start[e.first + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } auto counter = start; for (auto e : edges) { elist[counter[e.first]++] = e.second; } } }; } // namespace internal } // namespace atcoder #include <vector> namespace atcoder { namespace internal { template <class T> struct simple_queue { std::vector<T> payload; int pos = 0; void reserve(int n) { payload.reserve(n); } int size() const { return int(payload.size()) - pos; } bool empty() const { return pos == int(payload.size()); } void push(const T& t) { payload.push_back(t); } T& front() { return payload[pos]; } void clear() { payload.clear(); pos = 0; } void pop() { pos++; } }; } // namespace internal } // namespace atcoder namespace atcoder { template <class Cap, class Cost> struct mcf_graph { public: mcf_graph() {} mcf_graph(int n) : _n(n) {} int add_edge(int from, int to, Cap cap, Cost cost) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); assert(0 <= cost); int m = int(_edges.size()); _edges.push_back({from, to, cap, 0, cost}); return m; } struct edge { int from, to; Cap cap, flow; Cost cost; }; edge get_edge(int i) { int m = int(_edges.size()); assert(0 <= i && i < m); return _edges[i]; } std::vector<edge> edges() { return _edges; } std::pair<Cap, Cost> flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); } std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) { return slope(s, t, flow_limit).back(); } std::vector<std::pair<Cap, Cost>> slope(int s, int t) { return slope(s, t, std::numeric_limits<Cap>::max()); } std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); int m = int(_edges.size()); std::vector<int> edge_idx(m); auto g = [&]() { std::vector<int> degree(_n), redge_idx(m); std::vector<std::pair<int, _edge>> elist; elist.reserve(2 * m); for (int i = 0; i < m; i++) { auto e = _edges[i]; edge_idx[i] = degree[e.from]++; redge_idx[i] = degree[e.to]++; elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}}); elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}}); } auto _g = internal::csr<_edge>(_n, elist); for (int i = 0; i < m; i++) { auto e = _edges[i]; edge_idx[i] += _g.start[e.from]; redge_idx[i] += _g.start[e.to]; _g.elist[edge_idx[i]].rev = redge_idx[i]; _g.elist[redge_idx[i]].rev = edge_idx[i]; } return _g; }(); auto result = slope(g, s, t, flow_limit); for (int i = 0; i < m; i++) { auto e = g.elist[edge_idx[i]]; _edges[i].flow = _edges[i].cap - e.cap; } return result; } private: int _n; std::vector<edge> _edges; struct _edge { int to, rev; Cap cap; Cost cost; }; std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g, int s, int t, Cap flow_limit) { std::vector<std::pair<Cost, Cost>> dual_dist(_n); std::vector<int> prev_e(_n); std::vector<bool> vis(_n); struct Q { Cost key; int to; bool operator<(Q r) const { return key > r.key; } }; std::vector<int> que_min; std::vector<Q> que; auto dual_ref = [&]() { for (int i = 0; i < _n; i++) { dual_dist[i].second = std::numeric_limits<Cost>::max(); } std::fill(vis.begin(), vis.end(), false); que_min.clear(); que.clear(); size_t heap_r = 0; dual_dist[s].second = 0; que_min.push_back(s); while (!que_min.empty() || !que.empty()) { int v; if (!que_min.empty()) { v = que_min.back(); que_min.pop_back(); } else { while (heap_r < que.size()) { heap_r++; std::push_heap(que.begin(), que.begin() + heap_r); } v = que.front().to; std::pop_heap(que.begin(), que.end()); que.pop_back(); heap_r--; } if (vis[v]) continue; vis[v] = true; if (v == t) break; Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second; for (int i = g.start[v]; i < g.start[v + 1]; i++) { auto e = g.elist[i]; if (!e.cap) continue; Cost cost = e.cost - dual_dist[e.to].first + dual_v; if (dual_dist[e.to].second - dist_v > cost) { Cost dist_to = dist_v + cost; dual_dist[e.to].second = dist_to; prev_e[e.to] = e.rev; if (dist_to == dist_v) { que_min.push_back(e.to); } else { que.push_back(Q{dist_to, e.to}); } } } } if (!vis[t]) { return false; } for (int v = 0; v < _n; v++) { if (!vis[v]) continue; dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second; } return true; }; Cap flow = 0; Cost cost = 0, prev_cost_per_flow = -1; std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}}; while (flow < flow_limit) { if (!dual_ref()) break; Cap c = flow_limit - flow; for (int v = t; v != s; v = g.elist[prev_e[v]].to) { c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap); } for (int v = t; v != s; v = g.elist[prev_e[v]].to) { auto& e = g.elist[prev_e[v]]; e.cap += c; g.elist[e.rev].cap -= c; } Cost d = -dual_dist[s].first; flow += c; cost += c * d; if (prev_cost_per_flow == d) { result.pop_back(); } result.push_back({flow, cost}); prev_cost_per_flow = d; } return result; } }; } // namespace atcoder using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = (n)-1; i >= 0; --i) template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; ll m; cin >> n >> m; VI a(n), b(n), c(n); rep(i, n) { cin >> a[i] >> b[i] >> c[i]; if (a[i] > c[i]) swap(a[i], c[i]); } sort(all(b)); int lb = 0, rb = lb + n, bb = rb + n, acb = bb + n, s = acb + n, t = s + 1; mcf_graph<int, ll> g(t + 1); ll t_height = 1001001001LL * (n + 10); VL r_height(n); rep(i, n) r_height[i] = 1001001001LL * (i + 1); rep(i, n - 1) { g.add_edge(lb + i + 1, lb + i, 5000, 0); } rep(i, n) { g.add_edge(lb + i, bb + i, 1, 0); } rep(i, n - 1) { g.add_edge(rb + i, rb + i + 1, 5000, r_height[i + 1] - r_height[i] - (b[i + 1] - b[i])); } rep(i, n) { g.add_edge(rb + i, bb + i, 1, t_height - r_height[i]); } rep(i, n) { g.add_edge(bb + i, t, 1, 0); } rep(i, n) { g.add_edge(s, acb + i, 1, 0); } rep(i, n) { int u = lower_bound(all(b), a[i]) - b.begin(); --u; if (u >= 0) { g.add_edge(acb + i, lb + u, 1, t_height - c[i]); } int v = upper_bound(all(b), c[i]) - b.begin(); if (v < n) { g.add_edge(acb + i, rb + v, 1, r_height[v] - b[v]); } } auto [cap, cost] = g.flow(s, t); if (cap != n) { cout << "NO\n"; return 0; } cout << "YES\n"; cost -= t_height * n; cost = -cost; if (cost >= m) { cout << "KADOMATSU!" << '\n'; } else { cout << "NO" << '\n'; } }