結果
| 問題 |
No.1341 真ん中を入れ替えて門松列
|
| コンテスト | |
| ユーザー |
 tute7627
|
| 提出日時 | 2021-01-15 23:32:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,990 bytes |
| コンパイル時間 | 2,678 ms |
| コンパイル使用メモリ | 220,284 KB |
| 最終ジャッジ日時 | 2025-01-17 20:45:25 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 5 TLE * 9 |
ソースコード
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a) (a).begin(),(a).end()
#define ALLR(a) (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}
template<typename T>void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++){for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << p.first << " " << p.second;}
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){for(auto &z:v)os << z << " ";cout<<"|"; return os;}
template<typename T>void rearrange(vector<ll>&ord, vector<T>&v){
auto tmp = v;
for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
}
template<typename Head, typename... Tail>void rearrange(vector<ll>&ord,Head&& head, Tail&&... tail){
rearrange(ord, head);
rearrange(ord, tail...);
}
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int popcount(ll x){return __builtin_popcountll(x);};
int poplow(ll x){return __builtin_ctzll(x);};
int pophigh(ll x){return 63 - __builtin_clzll(x);};
namespace atcoder {
template <class Cap, class Cost> struct mcf_graph {
public:
mcf_graph() {}
mcf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap, Cost cost) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
g[from].push_back(_edge{to, int(g[to].size()), cap, cost});
g[to].push_back(_edge{from, int(g[from].size()) - 1, 0, -cost});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
Cost cost;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{
pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result(m);
for (int i = 0; i < m; i++) {
result[i] = get_edge(i);
}
return result;
}
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);
// variants (C = maxcost):
// -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
// reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge
std::vector<Cost> dual(_n, 0), dist(_n);
std::vector<int> pv(_n), pe(_n);
std::vector<bool> vis(_n);
auto dual_ref = [&]() {
std::fill(dist.begin(), dist.end(),
std::numeric_limits<Cost>::max());
std::fill(pv.begin(), pv.end(), -1);
std::fill(pe.begin(), pe.end(), -1);
std::fill(vis.begin(), vis.end(), false);
struct Q {
Cost key;
int to;
bool operator<(Q r) const { return key > r.key; }
};
std::priority_queue<Q> que;
dist[s] = 0;
que.push(Q{0, s});
while (!que.empty()) {
int v = que.top().to;
que.pop();
if (vis[v]) continue;
vis[v] = true;
if (v == t) break;
// dist[v] = shortest(s, v) + dual[s] - dual[v]
// dist[v] >= 0 (all reduced cost are positive)
// dist[v] <= (n-1)C
for (int i = 0; i < int(g[v].size()); i++) {
auto e = g[v][i];
if (vis[e.to] || !e.cap) continue;
// |-dual[e.to] + dual[v]| <= (n-1)C
// cost <= C - -(n-1)C + 0 = nC
Cost cost = e.cost - dual[e.to] + dual[v];
if (dist[e.to] - dist[v] > cost) {
dist[e.to] = dist[v] + cost;
pv[e.to] = v;
pe[e.to] = i;
que.push(Q{dist[e.to], e.to});
}
}
}
if (!vis[t]) {
return false;
}
for (int v = 0; v < _n; v++) {
if (!vis[v]) continue;
// dual[v] = dual[v] - dist[t] + dist[v]
// = dual[v] - (shortest(s, t) + dual[s] - dual[t]) + (shortest(s, v) + dual[s] - dual[v])
// = - shortest(s, t) + dual[t] + shortest(s, v)
// = shortest(s, v) - shortest(s, t) >= 0 - (n-1)C
dual[v] -= dist[t] - dist[v];
}
return true;
};
Cap flow = 0;
Cost cost = 0, prev_cost = -1;
std::vector<std::pair<Cap, Cost>> result;
result.push_back({flow, cost});
while (flow < flow_limit) {
if (!dual_ref()) break;
Cap c = flow_limit - flow;
for (int v = t; v != s; v = pv[v]) {
c = std::min(c, g[pv[v]][pe[v]].cap);
}
for (int v = t; v != s; v = pv[v]) {
auto& e = g[pv[v]][pe[v]];
e.cap -= c;
g[v][e.rev].cap += c;
}
Cost d = -dual[s];
flow += c;
cost += c * d;
if (prev_cost == d) {
result.pop_back();
}
result.push_back({flow, cost});
prev_cost = cost;
}
return result;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
Cost cost;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
} // namespace atcoder
using namespace atcoder;
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
ll res=0,buf=0;
bool judge = true;
ll n,m;cin>>n>>m;
mcf_graph<int,ll>pr(4*n+2);
ll S=4*n,T=4*n+1;
ll inf=1e14;
vector<ll>a(n),b(n),c(n);
vector<ll>vl,vr;
rep(i,0,n){
cin>>a[i]>>b[i]>>c[i];
if(a[i]==c[i])judge=false;
if(a[i]>c[i])swap(a[i],c[i]);
vl.PB(a[i]);
vr.PB(c[i]);
}
sort(ALL(vl));
sort(ALL(vr));
rep(i,0,n){
pr.add_edge(S,i,1,0);
ll l=upper_bound(ALL(vl),b[i])-vl.begin();
if(l<n)pr.add_edge(i,l+n,1,0);
ll r=--lower_bound(ALL(vr),b[i])-vr.begin();
if(r>=0)pr.add_edge(i,r+n+n,1,inf-b[i]);
}
rep(i,0,n-1){
pr.add_edge(i+n,i+1+n,n,0);
pr.add_edge(i+1+n+n,i+n+n,n,0);
}
rep(i,0,n){
ll l=lower_bound(ALL(vl),a[i])-vl.begin();
ll r=lower_bound(ALL(vr),c[i])-vr.begin();
pr.add_edge(l+n,i+3*n,1,inf-c[i]);
pr.add_edge(r+n+n,i+3*n,1,0);
pr.add_edge(i+3*n,T,1,0);
}
auto cc=pr.flow(S,T);
//pr.output();
//cout<<inf*n-cc<<endl;
if(cc.fi<n||!judge)cout<<"NO"<<endl;
else{
ans2(1);
ans(inf*n-cc.se>=m,"KADOMATSU!","NO");
}
return 0;
}