Submission #19661320


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

template <class E> struct csr {
  vector<int> start;
  vector<E> elist;
  csr(int n, const vector<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;
    }
  }
};

template <class T> struct simple_queue {
  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++; }
};

template <class Cap, class Cost> struct MinCostFlow {
public:
  MinCostFlow() {}
  MinCostFlow(int n) : _n(n) {}

  int add(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];
  }
  vector<edge> edges() { return _edges; }

  pair<Cap, Cost> flow(int s, int t) { return flow(s, t, numeric_limits<Cap>::max()); }
  pair<Cap, Cost> flow(int s, int t, Cap flow_limit) { return slope(s, t, flow_limit).back(); }
  vector<pair<Cap, Cost>> slope(int s, int t) { return slope(s, t, numeric_limits<Cap>::max()); }
  vector<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());
    vector<int> edge_idx(m);

    auto g = [&]() {
      vector<int> degree(_n), redge_idx(m);
      vector<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 = 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;
  vector<edge> _edges;
  struct _edge {
    int to, rev;
    Cap cap;
    Cost cost;
  };

  vector<pair<Cap, Cost>> slope(csr<_edge>& g, int s, int t, Cap flow_limit) {
    vector<pair<Cost, Cost>> dual_dist(_n);
    vector<int> prev_e(_n);
    vector<bool> vis(_n);
    struct Q {
      Cost key;
      int to;
      bool operator<(Q r) const { return key > r.key; }
    };
    vector<int> que_min;
    vector<Q> que;
    auto dual_ref = [&]() {
      for (int i = 0; i < _n; i++) {
        dual_dist[i].second = numeric_limits<Cost>::max();
      }
      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++;
            push_heap(que.begin(), que.begin() + heap_r);
          }
          v = que.front().to;
          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;
    vector<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 = 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;
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int R, G, B;
  cin >> R >> G >> B;

  int N = 1003;
  MinCostFlow<int, int> MC(N);
  MC.add(1001, 400, R, 0);
  MC.add(1001, 500, G, 0);
  MC.add(1001, 600, B, 0);
  for (int i = 0; i + 1 <= 1000; i++) {
    MC.add(i, i + 1, 1000, 1);
    MC.add(i + 1, i, 1000, 1);
  }
  for (int i = 0; i <= 1000; i++) {
    MC.add(i, 1002, 1, 0);
  }
  cout << MC.flow(1001, 1002, R + G + B).second << '\n';
}

Submission Info

Submission Time
Task D - マーブル
User ninoi
Language C++ (GCC 9.2.1)
Score 100
Code Size 6593 Byte
Status AC
Exec Time 18 ms
Memory 3800 KB

Judge Result

Set Name sub1 sub2 All
Score / Max Score 10 / 10 30 / 30 60 / 60
Status
AC × 29
AC × 57
AC × 85
Set Name Test Cases
sub1 sample_01_ABC.txt, test_ABC_01.txt, test_ABC_02.txt, test_ABC_03.txt, test_ABC_04.txt, test_ABC_05.txt, test_ABC_06.txt, test_ABC_07.txt, test_ABC_08.txt, test_ABC_09.txt, test_ABC_10.txt, test_ABC_11.txt, test_ABC_12.txt, test_ABC_13.txt, test_ABC_14.txt, test_ABC_15.txt, test_ABC_16.txt, test_ABC_17.txt, test_ABC_18.txt, test_ABC_19.txt, test_ABC_20.txt, test_ABC_21.txt, test_ABC_22.txt, test_ABC_23.txt, test_ABC_24.txt, test_ABC_25.txt, test_ABC_26.txt, test_ABC_27.txt, test_ABC_28.txt
sub2 sample_01_ABC.txt, sample_02_BC.txt, test_ABC_01.txt, test_ABC_02.txt, test_ABC_03.txt, test_ABC_04.txt, test_ABC_05.txt, test_ABC_06.txt, test_ABC_07.txt, test_ABC_08.txt, test_ABC_09.txt, test_ABC_10.txt, test_ABC_11.txt, test_ABC_12.txt, test_ABC_13.txt, test_ABC_14.txt, test_ABC_15.txt, test_ABC_16.txt, test_ABC_17.txt, test_ABC_18.txt, test_ABC_19.txt, test_ABC_20.txt, test_ABC_21.txt, test_ABC_22.txt, test_ABC_23.txt, test_ABC_24.txt, test_ABC_25.txt, test_ABC_26.txt, test_ABC_27.txt, test_ABC_28.txt, test_BC_29.txt, test_BC_30.txt, test_BC_31.txt, test_BC_32.txt, test_BC_33.txt, test_BC_34.txt, test_BC_35.txt, test_BC_36.txt, test_BC_37.txt, test_BC_38.txt, test_BC_39.txt, test_BC_40.txt, test_BC_41.txt, test_BC_42.txt, test_BC_43.txt, test_BC_44.txt, test_BC_45.txt, test_BC_46.txt, test_BC_47.txt, test_BC_48.txt, test_BC_49.txt, test_BC_50.txt, test_BC_51.txt, test_BC_52.txt, test_BC_53.txt, test_BC_54.txt, test_BC_55.txt
All sample_01_ABC.txt, sample_02_BC.txt, sample_03_C.txt, test_ABC_01.txt, test_ABC_02.txt, test_ABC_03.txt, test_ABC_04.txt, test_ABC_05.txt, test_ABC_06.txt, test_ABC_07.txt, test_ABC_08.txt, test_ABC_09.txt, test_ABC_10.txt, test_ABC_11.txt, test_ABC_12.txt, test_ABC_13.txt, test_ABC_14.txt, test_ABC_15.txt, test_ABC_16.txt, test_ABC_17.txt, test_ABC_18.txt, test_ABC_19.txt, test_ABC_20.txt, test_ABC_21.txt, test_ABC_22.txt, test_ABC_23.txt, test_ABC_24.txt, test_ABC_25.txt, test_ABC_26.txt, test_ABC_27.txt, test_ABC_28.txt, test_BC_29.txt, test_BC_30.txt, test_BC_31.txt, test_BC_32.txt, test_BC_33.txt, test_BC_34.txt, test_BC_35.txt, test_BC_36.txt, test_BC_37.txt, test_BC_38.txt, test_BC_39.txt, test_BC_40.txt, test_BC_41.txt, test_BC_42.txt, test_BC_43.txt, test_BC_44.txt, test_BC_45.txt, test_BC_46.txt, test_BC_47.txt, test_BC_48.txt, test_BC_49.txt, test_BC_50.txt, test_BC_51.txt, test_BC_52.txt, test_BC_53.txt, test_BC_54.txt, test_BC_55.txt, test_C_56.txt, test_C_57.txt, test_C_58.txt, test_C_59.txt, test_C_60.txt, test_C_61.txt, test_C_62.txt, test_C_63.txt, test_C_64.txt, test_C_65.txt, test_C_66.txt, test_C_67.txt, test_C_68.txt, test_C_69.txt, test_C_70.txt, test_C_71.txt, test_C_72.txt, test_C_73.txt, test_C_74.txt, test_C_75.txt, test_C_76.txt, test_C_77.txt, test_C_78.txt, test_C_79.txt, test_C_80.txt, test_C_81.txt, test_C_82.txt
Case Name Status Exec Time Memory
sample_01_ABC.txt AC 9 ms 3800 KB
sample_02_BC.txt AC 4 ms 3584 KB
sample_03_C.txt AC 13 ms 3640 KB
test_ABC_01.txt AC 2 ms 3800 KB
test_ABC_02.txt AC 4 ms 3748 KB
test_ABC_03.txt AC 2 ms 3636 KB
test_ABC_04.txt AC 2 ms 3752 KB
test_ABC_05.txt AC 2 ms 3708 KB
test_ABC_06.txt AC 6 ms 3784 KB
test_ABC_07.txt AC 5 ms 3748 KB
test_ABC_08.txt AC 4 ms 3752 KB
test_ABC_09.txt AC 3 ms 3644 KB
test_ABC_10.txt AC 3 ms 3752 KB
test_ABC_11.txt AC 4 ms 3648 KB
test_ABC_12.txt AC 2 ms 3644 KB
test_ABC_13.txt AC 3 ms 3708 KB
test_ABC_14.txt AC 3 ms 3756 KB
test_ABC_15.txt AC 3 ms 3640 KB
test_ABC_16.txt AC 2 ms 3724 KB
test_ABC_17.txt AC 2 ms 3712 KB
test_ABC_18.txt AC 3 ms 3712 KB
test_ABC_19.txt AC 2 ms 3592 KB
test_ABC_20.txt AC 3 ms 3752 KB
test_ABC_21.txt AC 2 ms 3648 KB
test_ABC_22.txt AC 3 ms 3784 KB
test_ABC_23.txt AC 3 ms 3756 KB
test_ABC_24.txt AC 2 ms 3788 KB
test_ABC_25.txt AC 3 ms 3756 KB
test_ABC_26.txt AC 3 ms 3712 KB
test_ABC_27.txt AC 3 ms 3632 KB
test_ABC_28.txt AC 3 ms 3716 KB
test_BC_29.txt AC 3 ms 3752 KB
test_BC_30.txt AC 3 ms 3644 KB
test_BC_31.txt AC 4 ms 3752 KB
test_BC_32.txt AC 3 ms 3800 KB
test_BC_33.txt AC 3 ms 3756 KB
test_BC_34.txt AC 3 ms 3704 KB
test_BC_35.txt AC 3 ms 3696 KB
test_BC_36.txt AC 3 ms 3800 KB
test_BC_37.txt AC 6 ms 3760 KB
test_BC_38.txt AC 3 ms 3636 KB
test_BC_39.txt AC 6 ms 3756 KB
test_BC_40.txt AC 3 ms 3756 KB
test_BC_41.txt AC 4 ms 3692 KB
test_BC_42.txt AC 3 ms 3648 KB
test_BC_43.txt AC 3 ms 3752 KB
test_BC_44.txt AC 4 ms 3712 KB
test_BC_45.txt AC 3 ms 3752 KB
test_BC_46.txt AC 3 ms 3712 KB
test_BC_47.txt AC 4 ms 3640 KB
test_BC_48.txt AC 6 ms 3712 KB
test_BC_49.txt AC 5 ms 3640 KB
test_BC_50.txt AC 3 ms 3752 KB
test_BC_51.txt AC 4 ms 3752 KB
test_BC_52.txt AC 3 ms 3708 KB
test_BC_53.txt AC 2 ms 3744 KB
test_BC_54.txt AC 4 ms 3632 KB
test_BC_55.txt AC 4 ms 3708 KB
test_C_56.txt AC 5 ms 3800 KB
test_C_57.txt AC 16 ms 3756 KB
test_C_58.txt AC 15 ms 3644 KB
test_C_59.txt AC 7 ms 3752 KB
test_C_60.txt AC 5 ms 3708 KB
test_C_61.txt AC 7 ms 3744 KB
test_C_62.txt AC 6 ms 3644 KB
test_C_63.txt AC 9 ms 3756 KB
test_C_64.txt AC 5 ms 3640 KB
test_C_65.txt AC 9 ms 3744 KB
test_C_66.txt AC 7 ms 3800 KB
test_C_67.txt AC 10 ms 3640 KB
test_C_68.txt AC 8 ms 3632 KB
test_C_69.txt AC 4 ms 3752 KB
test_C_70.txt AC 6 ms 3752 KB
test_C_71.txt AC 11 ms 3632 KB
test_C_72.txt AC 12 ms 3588 KB
test_C_73.txt AC 11 ms 3752 KB
test_C_74.txt AC 8 ms 3756 KB
test_C_75.txt AC 14 ms 3760 KB
test_C_76.txt AC 14 ms 3752 KB
test_C_77.txt AC 9 ms 3716 KB
test_C_78.txt AC 14 ms 3708 KB
test_C_79.txt AC 6 ms 3644 KB
test_C_80.txt AC 7 ms 3696 KB
test_C_81.txt AC 6 ms 3752 KB
test_C_82.txt AC 18 ms 3632 KB