結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー emthrm
提出日時 2021-01-15 22:58:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,097 bytes
コンパイル時間 3,503 ms
コンパイル使用メモリ 216,484 KB
最終ジャッジ日時 2025-01-17 20:20:44
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 2 TLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

// https://github.com/beet-aizu/library/tree/master/mincostflow
template<typename Flow, typename Cost>
struct PrimalDual{
  struct Edge{
    int dst;
    Flow cap;
    Cost cost;
    int rev;
    Edge(int dst,Flow cap,Cost cost,int rev):
      dst(dst),cap(cap),cost(cost),rev(rev){}
  };

  vector<vector<Edge>> G;
  vector<Cost> h,dist;
  vector<int> prevv,preve;

  PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){}

  void add_edge(int u,int v,Flow cap,Cost cost){
    int e=G[u].size();
    int r=(u==v?e+1:G[v].size());
    G[u].emplace_back(v,cap,cost,r);
    G[v].emplace_back(u,0,-cost,e);
  }

  Cost residual_cost(int src,Edge &e){
    return e.cost+h[src]-h[e.dst];
  }

  void dijkstra(int s){
    struct P{
      Cost first;
      int second;
      P(Cost first,int second):first(first),second(second){}
      bool operator<(const P&a) const{return first>a.first;}
    };
    priority_queue<P> pq;

    dist[s]=0;
    pq.emplace(dist[s],s);
    while(!pq.empty()){
      P p=pq.top();pq.pop();
      int v=p.second;
      if(dist[v]<p.first) continue;
      for(int i=0;i<(int)G[v].size();i++){
        Edge &e=G[v][i];
        if(e.cap==0) continue;
        if(!(dist[v]+residual_cost(v,e)<dist[e.dst])) continue;
        dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst];
        prevv[e.dst]=v;
        preve[e.dst]=i;
        pq.emplace(dist[e.dst],e.dst);
      }
    }
  }

  Cost res;

  bool build(int s,int t,Flow f,
             function<void(decltype(h)&)> init=[](decltype(h) &p){
               fill(p.begin(),p.end(),0);
             }){
    res=0;
    init(h);
    const Cost INF = numeric_limits<Cost>::max();
    while(f>0){
      fill(dist.begin(),dist.end(),INF);
      dijkstra(s);
      if(dist[t]==INF) return false;

      for(int v=0;v<(int)h.size();v++)
        if(dist[v]<INF) h[v]=h[v]+dist[v];

      Flow d=f;
      for(int v=t;v!=s;v=prevv[v])
        d=min(d,G[prevv[v]][preve[v]].cap);

      f-=d;
      res=res+h[t]*d;
      for(int v=t;v!=s;v=prevv[v]){
        Edge &e=G[prevv[v]][preve[v]];
        e.cap-=d;
        G[v][e.rev].cap+=d;
      }
    }
    return true;
  }

  Cost get_cost(){return res;}
};

template<typename Flow, typename Cost>
struct NegativeEdge{
  PrimalDual<Flow, Cost> G;
  vector<Flow> fs;
  Cost sum;
  int S,T;
  NegativeEdge(int n):G(n+2),fs(n+2,0),sum(0),S(n),T(n+1){}

  void use_edge(int u,int v,Flow cap,Cost cost){
    fs[u]-=cap;
    fs[v]+=cap;
    sum=sum+cost*cap;
  }

  void add_edge(int u,int v,Flow cap,Cost cost){
    if(cost<Cost(0)){
      use_edge(u,v,cap,cost);
      swap(u,v);
      cost=-cost;
    }
    G.add_edge(u,v,cap,cost);
  }

  bool build(){
    Flow f=0;
    for(int i=0;i<S;i++){
      if(fs[i]>0){
        f+=fs[i];
        G.add_edge(S,i,+fs[i],Cost(0));
      }
      if(fs[i]<0){
        G.add_edge(i,T,-fs[i],Cost(0));
      }
    }
    return G.build(S,T,f);
  }

  bool build(int ts,int tt,Flow tf){
    fs[ts]+=tf;
    fs[tt]-=tf;
    return build();
  }

  Cost get_cost(){
    return sum+G.get_cost();
  }
};

int main() {
  int n; ll m; cin >> n >> m;
  vector<int> 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]);
  }
  vector<int> a_ord(n), c_ord(n);
  iota(ALL(a_ord), 0);
  sort(ALL(a_ord), [&](int x, int y) { return a[x] < a[y]; });
  sort(ALL(b));
  iota(ALL(c_ord), 0);
  sort(ALL(c_ord), [&](int x, int y) { return c[x] > c[y]; });

  NegativeEdge<int, ll> pd(n * 3 + 2);
  const int s = n * 3, t = n * 3 + 1;
  REP(i, n) pd.add_edge(s, i, 1, 0);
  FOR(i, 1, n) pd.add_edge(n + a_ord[i - 1], n + a_ord[i], n, 0);
  int idx = 0;
  REP(i, n) {
    for (; idx < n && b[idx] < a[a_ord[i]]; ++idx) {
      pd.add_edge(idx, n + a_ord[i], 1, 0);
    }
  }
  FOR(i, 1, n) pd.add_edge(n + n + c_ord[i - 1], n + n + c_ord[i], n, 0);
  idx = n - 1;
  REP(i, n) {
    for (; idx >= 0 && b[idx] > c[c_ord[i]]; --idx) {
      pd.add_edge(idx, n + n + c_ord[i], 1, -b[idx]);
    }
  }
  REP(i, n) {
    pd.add_edge(n + i, n + n + i, 1, -c[i]);
    pd.add_edge(n + n + i, t, 1, 0);
  }
  if (pd.build(s, t, n)) {
    cout << "YES\n" << (-pd.get_cost() >= m ? "KADOMATSU!\n" : "NO\n");
  } else {
    cout << "NO\n";
  }
  return 0;
}
0