#604706 (C++17) No.1341 真ん中を入れ替えて門松列

提出ソース

結果

問題	No.1341 真ん中を入れ替えて門松列
ユーザー	ei1333333
提出日時	2021-01-15 23:15:23
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,731 bytes
コンパイル時間	2,687 ms
コンパイル使用メモリ	227,792 KB
実行使用メモリ	17,024 KB
最終ジャッジ日時	2024-11-26 17:25:30
合計ジャッジ時間	37,320 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 11,136 KB
testcase_01	AC	2 ms 10,496 KB
testcase_02	AC	2 ms 10,624 KB
testcase_03	AC	2 ms 11,264 KB
testcase_04	AC	2 ms 10,624 KB
testcase_05	AC	1 ms 11,520 KB
testcase_06	AC	21 ms 10,624 KB
testcase_07	AC	606 ms 12,288 KB
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
//const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


template< typename key_t, typename val_t >
struct RadixHeap {
  static constexpr int bit = sizeof(key_t) * 8;
  array< vector< pair< key_t, val_t > >, bit > vs;

  size_t sz;
  key_t last;

  RadixHeap() : sz(0), last(0) {}

  bool empty() const { return sz == 0; }

  size_t size() const { return sz; }

  inline int getbit(int a) const {
    return a ? bit - __builtin_clz(a) : 0;
  }

  inline int getbit(int64_t a) const {
    return a ? bit - __builtin_clzll(a) : 0;
  }

  void push(const key_t &key, const val_t &val) {
    sz++;
    vs[getbit(key ^ last)].emplace_back(key, val);
  }

  pair< key_t, val_t > pop() {
    if(vs[0].empty()) {
      int idx = 1;
      while(vs[idx].empty()) idx++;
      last = min_element(vs[idx].begin(), vs[idx].end())->first;
      for(auto &p:vs[idx]) vs[getbit(p.first ^ last)].emplace_back(p);
      vs[idx].clear();
    }
    --sz;
    auto res = vs[0].back();
    vs[0].pop_back();
    return res;
  }
};

//BEGIN CUT HERE
// O(m^2 \log m \log U)
// U: maximum capacity
enum Objective {
  MINIMIZE = +1,
  MAXIMIZE = -1,
};

template< typename Flow, typename Cost,
    Objective objective = Objective::MINIMIZE >
struct MinCostFlow {
  template< typename T >
  inline void chmin(T &x, T y) { x = min(x, y); }

  struct Edge {
    int src, dst;
    Flow flow, cap;
    Cost cost;
    int rev;

    Edge(int src, int dst, Flow cap, Cost cost, int rev) :
        src(src), dst(dst), flow(0), cap(cap), cost(cost), rev(rev) {}

    Flow residual_cap() const { return cap - flow; }
  };

  struct EdgePtr {
    int v, e;

    EdgePtr(int v, int e) : v(v), e(e) {}
  };

  int n;
  vector< vector< Edge>> G;
  vector< Flow > b;
  vector< Cost > p;

  MinCostFlow(int n) : n(n), G(n), b(n, 0) {}

  EdgePtr add_edge(int src, int dst, Flow lower, Flow upper, Cost cost) {
    int e = G[src].size();
    int r = (src == dst ? e + 1 : G[dst].size());
    assert(lower <= upper);
    G[src].emplace_back(src, dst, +upper, +cost * objective, r);
    G[dst].emplace_back(dst, src, -lower, -cost * objective, e);
    return EdgePtr(src, e);
  }

  const Edge &get_edge(EdgePtr ep) const { return G[ep.v][ep.e]; }

  void push(Edge &e, Flow amount) {
    e.flow += amount;
    G[e.dst][e.rev].flow -= amount;
  }

  void add_supply(int v, Flow amount) { b[v] += amount; }

  void add_demand(int v, Flow amount) { b[v] -= amount; }

  Cost residual_cost(const Edge &e) {
    return e.cost + p[e.src] - p[e.dst];
  }

  vector< int > excess_vs, deficit_vs;

  void saturate_negative(const Flow delta) {
    for(auto &es:G) {
      for(auto &e:es) {
        Flow cap = e.residual_cap();
        cap -= cap % delta;
        if(cap < 0 or residual_cost(e) < 0) {
          push(e, cap);
          b[e.src] -= cap;
          b[e.dst] += cap;
        }
      }
    }

    excess_vs.clear();
    deficit_vs.clear();
    for(int v = 0; v < n; v++) {
      if(b[v] > 0) excess_vs.emplace_back(v);
      if(b[v] < 0) deficit_vs.emplace_back(v);
    }
  }

  const Cost unreachable = std::numeric_limits< Cost >::max();
  Cost farthest;
  vector< Cost > dist;
  vector< Edge * > parent;

  struct P {
    Cost first;
    int second;

    P(Cost first, int second) : first(first), second(second) {}

    bool operator<(const P o) const { return first > o.first; }
  };

  priority_queue< P > pq;

  template< typename Predicate >
  void eliminate(vector< int > &vs, Predicate predicate) {
    vs.erase(remove_if(begin(vs), end(vs), predicate), end(vs));
  }

  bool dual(const Flow delta) {
    eliminate(excess_vs, [&](int v) { return b[v] < +delta; });
    eliminate(deficit_vs, [&](int v) { return b[v] > -delta; });

    dist.assign(n, unreachable);
    for(int v:excess_vs) pq.emplace(dist[v] = 0, v);

    parent.assign(n, nullptr);
    auto emplace = [&](Edge &e) {
      if(e.residual_cap() < delta) return;
      Cost nxt = dist[e.src] + residual_cost(e);
      if(nxt >= dist[e.dst]) return;
      pq.emplace(dist[e.dst] = nxt, e.dst);
      parent[e.dst] = &e;
    };

    farthest = 0;
    int deficit_count = 0;
    while(!pq.empty()) {
      Cost d = pq.top().first;
      int v = pq.top().second;
      pq.pop();
      if(dist[v] < d) continue;
      farthest = d;

      if(b[v] <= -delta) deficit_count++;
      if(deficit_count >= (int) deficit_vs.size()) break;

      for(auto &e:G[v]) emplace(e);
    }
    pq = decltype(pq)();

    for(int v = 0; v < n; v++)
      p[v] += min(dist[v], farthest);

    return deficit_count > 0;
  }

  void primal(const Flow delta) {
    for(int t:deficit_vs) {
      if(dist[t] > farthest) continue;
      Flow f = -b[t];
      int v;
      for(v = t; parent[v]; v = parent[v]->src)
        chmin(f, parent[v]->residual_cap());
      chmin(f, b[v]);

      f -= f % delta;
      if(f <= 0) continue;

      for(v = t; parent[v];) {
        auto &e = *parent[v];
        push(e, f);
        int u = parent[v]->src;
        if(e.residual_cap() <= 0) parent[v] = nullptr;
        v = u;
      }
      b[t] += f;
      b[v] -= f;
    }
  }

  template< Flow SCALING_FACTOR = 2 >
  bool build() {
    p.resize(n);
    Flow max_flow = 1;
    for(auto t:b) max_flow = max({max_flow, t, -t});
    for(auto &es:G)
      for(auto &e:es)
        max_flow = max({max_flow, e.residual_cap(), -e.residual_cap()});

    Flow delta = 1;
    while(delta < max_flow) delta *= SCALING_FACTOR;
    for(; delta; delta /= SCALING_FACTOR) {
      saturate_negative(delta);
      while(dual(delta)) primal(delta);
    }

    return excess_vs.empty() and deficit_vs.empty();
  }

  template< typename T=Cost >
  T get_cost() {
    T res = 0;
    for(auto &es:G)
      for(auto &e:es)
        res += T(e.flow) * T(e.cost) / T(objective);
    return res / T(2);
  }

  template< typename T=Cost >
  T get_gain() { return get_cost(); }

  vector< Cost > get_potential() {
    fill(p.begin(), p.end(), 0);
    for(int i = 0; i < n; i++)
      for(auto &es:G)
        for(auto &e:es)
          if(e.residual_cap() > 0)
            chmin(p[e.dst], p[e.src] + e.cost);
    return p;
  }
};

template< typename Flow, typename Cost >
using MaxGainFlow = MinCostFlow< Flow, Cost, Objective::MAXIMIZE >;

template< typename Flow, typename Cost >
using MinGainFlow = MinCostFlow< Flow, Cost, Objective::MINIMIZE >;


int main() {
  int N;
  int64 M;
  cin >> N >> M;
  vector< int > X(N), Y(N), Z(N);
  for(int i = 0; i < N; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    if(A > C) swap(A, C);
    X[i] = A;
    Y[i] = B;
    Z[i] = C;
  }
  sort(begin(Y), end(Y));

  MaxGainFlow< int, int64 > flow(N + N + N + N + 2);
  int S = N + N + N + N;
  int T = S + 1;

  // <-----
  for(int i = N - 2; i >= 0; i--) {
    flow.add_edge(i + N + 1, i + N, 0, N, 0);
  }
  // ---->
  for(int i = 1; i < N; i++) {
    flow.add_edge(i + N + N - 1, i + N + N, 0, N, 0);
  }
  for(int i = 0; i < N; i++) {
    flow.add_edge(i + N, i + N + N + N, 0, 1, 0);
    flow.add_edge(i + N + N, i + N + N + N, 0, 1, Y[i]);
    flow.add_edge(i + N + N + N, T, 0, 1, 0);
  }

  for(int i = 0; i < N; i++) {
    vector< int > ok(N);
    for(int j = 0; j < N; j++) {
      if(Y[j] < X[i]) ok[j] = 1;
      else if(Z[i] < Y[j]) ok[j] = 2;
    }
    flow.add_edge(S, i, 0, 1, 0);
    for(int j = 0; j < N; j++) {
      if(ok[j] == 2) {
        flow.add_edge(i, j + N + N, 0, 1, 0);
        break;
      }
    }
    for(int j = N - 1; j >= 0; j--) {
      if(ok[j] == 1) {
        flow.add_edge(i, j + N, 0, 1, Z[i]);
        break;
      }
    }
  }
  flow.add_supply(S, N);
  flow.add_demand(T, N);
  if(!flow.build()) {
    cout << "NO\n";
  } else {
    cout << "YES\n";
    auto ret = flow.get_cost();
    if(ret >= M) cout << "KADOMATSU!\n";
    else cout << "NO\n";
  }
}

yukicoder

結果

テストケース

ソースコード