結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー |
![]() |
提出日時 | 2021-01-15 23:50:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 914 ms / 2,000 ms |
コード長 | 9,570 bytes |
コンパイル時間 | 2,510 ms |
コンパイル使用メモリ | 222,364 KB |
最終ジャッジ日時 | 2025-01-17 20:51:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#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 atcodernamespace 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 atcoderusing 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';}}