#1186984 (C++23(gcc16)) No.3764 Graduation Live

• 問題: No.3764 Graduation Live
• ユーザー: ei1333333
• 提出日時: 2026-09-16 01:44:37
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 572 ms / 2,000 ms
• コード長: 9,815 bytes
• コンパイル時間: 3,203 ms
• コンパイル使用メモリ: 374,472 KB
• 実行使用メモリ: 17,592 KB
• 最終ジャッジ日時: 2026-10-09 20:50:50
• 合計ジャッジ時間: 27,189 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 45

ソースコード

#include <bits/stdc++.h>
#include <cassert>

using namespace std;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
  }
} iosetup;

// https://github.com/drken1215/algorithm/blob/master/NetworkFlow/min_cost_convex_flow.cpp
// edge class (for min convex-cost flow)
// cost-function must be convex
template<class FLOW, class COST>
struct FlowConvexCostEdge {
  using FUNC = function<COST(FLOW)>;

  // core members
  int rev, from, to;
  FLOW cap, icap, flow;
  FUNC cost;

  // constructor
  constexpr FlowConvexCostEdge() noexcept = default;

  constexpr FlowConvexCostEdge(int rev, int from, int to, FLOW cap, const FUNC &f)
    : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(0), cost(f) {
  }

  constexpr FlowConvexCostEdge(int rev, int from, int to, FLOW cap, FLOW rcap, const FUNC &f)
    : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(rcap), cost(f) {
  }

  void reset() {
    flow -= icap - cap;
    cap = icap;
  }

  constexpr COST get_next_cost() const {
    return cost(flow + 1) - cost(flow);
  }

  friend constexpr COST get_next_cost(const FlowConvexCostEdge &e) {
    return e.get_next_cost();
  }

  // debug
  friend ostream &operator <<(ostream &s, const FlowConvexCostEdge &e) {
    return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.flow << ")";
  }
};

// graph class (for min-cost flow)
template<class FLOW, class COST>
struct FlowConvexCostGraph {
  using FUNC = function<COST(FLOW)>;

  // core members
  vector<vector<FlowConvexCostEdge<FLOW, COST> > > list;
  vector<pair<int, int> > pos; // pos[i] := {vertex, order of list[vertex]} of i-th edge
  vector<COST> pot; // pot[v] := potential (e.cost + pot[e.from] - pos[e.to] >= 0)
  bool include_negative_edge = false;

  // constructor
  FlowConvexCostGraph(int n = 0) : list(n), pot(n), include_negative_edge(false) {
  }

  void init(int n = 0) {
    list.clear(), list.resize(n);
    pos.clear();
    pot.assign(n, 0);
    include_negative_edge = false;
  }

  // getter
  vector<FlowConvexCostEdge<FLOW, COST> > &operator [](int i) {
    assert(0 <= i && i < list.size());
    return list[i];
  }

  const vector<FlowConvexCostEdge<FLOW, COST> > &operator [](int i) const {
    assert(0 <= i && i < list.size());
    return list[i];
  }

  size_t size() const noexcept {
    return list.size();
  }

  size_t size_edegs() const noexcept {
    return pos.size();
  }

  FlowConvexCostEdge<FLOW, COST> &get_rev_edge(const FlowConvexCostEdge<FLOW, COST> &e) {
    return list[e.to][e.rev];
  }

  const FlowConvexCostEdge<FLOW, COST> &get_rev_edge(const FlowConvexCostEdge<FLOW, COST> &e) const {
    return list[e.to][e.rev];
  }

  FlowConvexCostEdge<FLOW, COST> &get_edge(int i) {
    return list[pos[i].first][pos[i].second];
  }

  const FlowConvexCostEdge<FLOW, COST> &get_edge(int i) const {
    return list[pos[i].first][pos[i].second];
  }

  vector<FlowConvexCostEdge<FLOW, COST> > get_edges() const {
    vector<FlowConvexCostEdge<FLOW, COST> > edges;
    for (int i = 0; i < (int) pos.size(); ++i) {
      edges.push_back(get_edge(i));
    }
    return edges;
  }

  // change edges
  void reset() {
    for (int i = 0; i < (int) list.size(); ++i) {
      for (FlowConvexCostEdge<FLOW, COST> &e: list[i]) e.reset();
    }
  }

  // add_edge
  void add_edge(int from, int to, FLOW cap, const FUNC &cost) {
    assert(0 <= from && from < list.size() && 0 <= to && to < list.size());
    assert(cap >= 0);
    int from_id = int(list[from].size()), to_id = int(list[to].size());
    if (from == to) to_id++;
    auto negcost = [cost, cap](FLOW f) -> COST { return cost(cap - f); };
    pos.emplace_back(from, from_id);
    list[from].push_back(FlowConvexCostEdge<FLOW, COST>(to_id, from, to, cap, 0, cost));
    list[to].push_back(FlowConvexCostEdge<FLOW, COST>(from_id, to, from, 0, cap, negcost));
    if (cost(1) - cost(0) < 0) include_negative_edge = true;
  }

  // find initial potential (to resolve initial negative-edge)
  // pot[v] := potential (e.cost + pot[e.from] - pos[e.to] >= 0)
  bool calc_potential_dag() {
    pot.assign(size(), 0);
    vector<int> deg(size(), 0), st;
    for (int v = 0; v < size(); v++) for (const auto &e: list[v]) deg[e.to] += (e.cap > 0);
    st.reserve(size());
    for (int v = 0; v < size(); v++) if (!deg[v]) st.emplace_back(v);
    for (int i = 0; i < size(); i++) {
      if (st.size() == i) return false; // not DAG
      int cur = st[i];
      for (const auto &e: list[cur]) {
        if (e.cap <= 0) continue;
        deg[e.to]--;
        if (deg[e.to] == 0) st.emplace_back(e.to);
        if (pot[e.to] >= pot[cur] + e.get_next_cost()) pot[e.to] = pot[cur] + e.get_next_cost();
      }
    }
    return true;
  }

  bool calc_potential_spfa() {
    pot.assign(size(), 0);
    queue<int> que;
    vector<bool> inque(size(), false);
    vector<int> cnt(size(), 0);
    for (int v = 0; v < size(); v++) que.push(v), inque[v] = true;
    while (!que.empty()) {
      int cur = que.front();
      que.pop();
      inque[cur] = false;
      if (cnt[cur] > size()) return false; // include negative-cycle
      cnt[cur]++;
      for (const auto &e: list[cur]) {
        if (e.cap <= 0) continue;
        if (pot[e.to] > pot[cur] + e.get_next_cost()) {
          pot[e.to] = pot[cur] + e.get_next_cost();
          if (!inque[e.to]) inque[e.to] = true, que.push(e.to);
        }
      }
    }
    return true;
  }

  bool calc_potential() {
    return calc_potential_dag() || calc_potential_spfa();
  }

  bool init_potential() {
    if (!include_negative_edge) return true;
    return calc_potential();
  }

  // debug
  friend ostream &operator <<(ostream &s, const FlowConvexCostGraph &G) {
    const auto &edges = G.get_edges();
    for (const auto &e: edges) s << e << endl;
    return s;
  }
};

// min-cost max-flow (<= limit_flow), slope ver.
template<class FLOW, class COST>
vector<pair<FLOW, COST> >
MinCostFlowSlope(FlowConvexCostGraph<FLOW, COST> &G, int S, int T, FLOW limit_flow) {
  // result values
  FLOW cur_flow = 0;
  COST cur_cost = 0, pre_cost = numeric_limits<COST>::max() / 2;
  vector<pair<FLOW, COST> > res;
  res.emplace_back(cur_flow, cur_cost);

  // intermediate values
  vector<COST> dist((int) G.size(), numeric_limits<COST>::max() / 2);
  vector<int> prevv((int) G.size(), -1), preve((int) G.size(), -1);

  // dual
  auto dual_step = [&]() -> bool {
    dist.assign((int) G.size(), numeric_limits<COST>::max() / 2);
    dist[S] = 0;
    priority_queue<pair<COST, int>, vector<pair<COST, int> >, greater<pair<COST, int> > > que;
    que.emplace(0, S);
    while (!que.empty()) {
      auto [cur, v] = que.top();
      que.pop();
      if (cur > dist[v]) continue;
      for (int i = 0; i < (int) G[v].size(); i++) {
        const auto &e = G[v][i];
        if (e.cap >= FLOW(1)) {
          COST add = e.get_next_cost() + G.pot[v] - G.pot[e.to];
          if (dist[e.to] > dist[v] + add) {
            dist[e.to] = dist[v] + add;
            prevv[e.to] = v;
            preve[e.to] = i;
            que.emplace(dist[e.to], e.to);
          }
        }
      }
    }
    return dist[T] < numeric_limits<COST>::max() / 2;
  };

  // primal
  auto primal_step = [&]() -> void {
    for (int v = 0; v < G.size(); v++) {
      if (dist[v] < numeric_limits<COST>::max() / 2) G.pot[v] += dist[v];
      else G.pot[v] = numeric_limits<COST>::max() / 2;
    }
    FLOW flow = 1; // 1 ずつ流す
    COST cost = G.pot[T] - G.pot[S];
    for (int v = T; v != S; v = prevv[v]) {
      FlowConvexCostEdge<FLOW, COST> &e = G[prevv[v]][preve[v]];
      FlowConvexCostEdge<FLOW, COST> &re = G.get_rev_edge(e);
      e.cap -= flow, e.flow += flow;
      re.cap += flow, re.flow -= flow;
    }
    cur_flow += flow;
    cur_cost += flow * cost;
    if (pre_cost == cost) res.pop_back();
    res.emplace_back(cur_flow, cur_cost);
    pre_cost = cost;
  };

  // initialize potential
  G.init_potential();

  // primal-dual
  while (cur_flow < limit_flow) {
    if (!dual_step()) break;
    primal_step();
  }
  return res;
}

// min-cost max-flow, slope ver.
template<class FLOW, class COST>
vector<pair<FLOW, COST> >
MinCostFlowSlope(FlowConvexCostGraph<FLOW, COST> &G, int S, int T) {
  return MinCostFlowSlope(G, S, T, numeric_limits<FLOW>::max());
}

using ll = long long;

void sub() {
  int N;
  vector<int> W(4);
  cin >> N >> W[1] >> W[2] >> W[3];
  W[0] = N;
  vector<int> vs[6];
  for (int i = 0; i < N; i++) {
    int t, v;
    cin >> t >> v;
    --t;
    vs[t].emplace_back(v);
  }
  vector<vector<ll> > sum(6);
  for (int i = 0; i < 6; i++) {
    sum[i].resize(vs[i].size() + 1);
    ranges::sort(vs[i], greater());
    for (int j = 0; j < vs[i].size(); j++) {
      sum[i][j + 1] = sum[i][j] + vs[i][j];
    }
  }
  FlowConvexCostGraph<int, ll> g(10);
  constexpr int edge[6][2] = {
    {0, 1}, {0, 2}, {0, 3},
    {1, 2}, {1, 3}, {2, 3}
  };
  constexpr int S = 8, T = 9;
  {
    auto zero = [](int) { return 0ll; };
    for (int i = 0; i < 4; i++) {
      g.add_edge(S, i, W[i], zero);
      g.add_edge(4 + i, T, W[i], zero);
    }
  }
  for (int t = 0; t < 6; t++) {
    if (int m = static_cast<int>(vs[t].size()); m > 0) {
      auto [u, v] = edge[t];
      auto cost = [&sum, t](int f) -> ll {
        return -sum[t][f];
      };
      g.add_edge(u, 4 + v, m, cost);
      g.add_edge(v, 4 + u, m, cost);
    }
  }
  auto slope = MinCostFlowSlope(g, S, T, 2 * N);
  auto C = slope.back().first / 2;
  cout << C ;
  auto p = 1;
  for (int c = 1; c <= C; c++) {
    auto f = 2 * c;
    while (slope[p].first < f) {
      p++;
    }
    auto [f0, cost0] = slope[p - 1];
    auto [f1, cost1] = slope[p];
    auto a = cost0 + (cost1 - cost0) / (f1 - f0) * (f - f0);
    cout << " " << -a / 2;
  }
  cout << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    sub();
  }
}