Submission #965079

#	Time	Username	Problem	Language	Result	Execution time	Memory
965079		happybelly	Closing Time (IOI23_closing)	C++17	100 / 100	298 ms	65312 KiB

closing

#include "closing.h"

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

typedef long long ll;

struct Fenwick {
  vector<ll> a;
  int size;
  int lg;

  Fenwick(int size_) {
    size = size_;
    a.resize(size + 1, 0);
    lg = 0;
    while ((1 << lg) <= size) lg++;
  }

  void add(int i, ll v) {
    for (; i <= size; i += i & -i) a[i] += v;
  }

  ll query(int i) {
    ll ans = 0;
    for (; i > 0; i -= i & -i) ans += a[i];
    return ans;
  }

  int lower_bound(ll v) {
    int idx = 0;
    ll sum = 0;
    for (int i = lg - 1; i >= 0; i--)
      if (idx + (1 << i) <= size && sum + a[idx + (1 << i)] < v) {
        idx += (1 << i);
        sum += a[idx];
      }
    return idx + 1;
  }
};

vector<ll> pval, qval;
vector<vector<tuple<int, int>>> gr;
vector<bool> inxy;
vector<int> parent;

int N;
ll K;

void dfs(int p, int u, ll d, vector<ll> &dist) {
  parent[u] = p;
  dist[u] = d;
  for (auto &t : gr[u]) {
    int v = get<0>(t);
    if (v != p) dfs(u, v, d + get<1>(t), dist);
  }
}

int GetScoreWithoutCommon() {
  vector<ll> pq;
  pq.insert(pq.end(), pval.begin(), pval.end());
  pq.insert(pq.end(), qval.begin(), qval.end());
  sort(pq.begin(), pq.end());

  ll total = 0;
  int ans = 0;
  for (auto &c : pq) {
    if (total + c <= K) {
      total += c;
      ans++;
    } else
      break;
  }
  return ans;
}

int GetScoreWithCommon() {
  ll total_xy = 0;
  int ans = 0;
  for (int i = 0; i < N; i++)
    if (inxy[i]) {
      total_xy += pval[i];
      qval[i] -= pval[i];
      pval[i] = 0;
    }

  vector<tuple<ll, ll, int>> diffs;
  for (int i = 0; i < N; i++) diffs.emplace_back(qval[i] - pval[i], pval[i], i);
  sort(diffs.begin(), diffs.end());

  vector<tuple<ll, int, int>> elem;
  for (int i = 0; i < N; i++) {
    elem.emplace_back(2 * pval[i], i, i);
    elem.emplace_back(qval[i], -2 * i - 1, i);
    elem.emplace_back(qval[i], -2 * i - 2, i);
  }
  elem.emplace_back(-1, 0, 0);
  sort(elem.begin(), elem.end());

  vector<int> pidx(N), qidx(N);
  for (int i = 1; i <= 3 * N; i++) {
    int j = get<2>(elem[i]);
    if (get<1>(elem[i]) >= 0)
      pidx[j] = i;
    else
      qidx[j] = i;
  }

  Fenwick prefix(3 * N), p_ctr(3 * N), q_ctr(3 * N);

  auto Knapsack01 = [&](ll cap) -> int {
    int idx = prefix.lower_bound(cap + 1) - 1;
    ll total = prefix.query(idx);
    int score = p_ctr.query(idx) + q_ctr.query(idx);

    if (q_ctr.query(idx) % 2 == 0) return score;

    int curr_p = p_ctr.lower_bound(p_ctr.query(idx)),
        curr_q = q_ctr.lower_bound(q_ctr.query(idx));
    if (p_ctr.query(idx) != p_ctr.query(3 * N)) {
      int next_p = p_ctr.lower_bound(p_ctr.query(idx) + 1);
      if (total - get<0>(elem[curr_q]) + get<0>(elem[next_p]) <= cap)
        return score;
    }

    if (curr_p > 0) {
      if (total - get<0>(elem[curr_p]) + get<0>(elem[curr_q]) <= cap)
        return score;
    }
    return score - 1;
  };

  for (int i = 0; i < N; i++) {
    int idx = pidx[i];
    prefix.add(idx, 2 * pval[i]);
    p_ctr.add(idx, 1);
  }

  for (int i = 0; i < N; i++) {
    int node = get<2>(diffs[i]);
    int idx = pidx[node];
    prefix.add(idx, -2 * pval[node]);
    p_ctr.add(idx, -1);

    idx = qidx[node];
    prefix.add(idx, qval[node]);
    prefix.add(idx - 1, qval[node]);
    q_ctr.add(idx, 1);
    q_ctr.add(idx - 1, 1);
    if (total_xy <= K) {
      int score = Knapsack01(2 * (K - total_xy));
      ans = max(ans, score);
    }
  }
  return ans;
}

int max_score(int N_, int X, int Y, ll K_, vector<int> U, vector<int> V,
              vector<int> W) {
  N = N_;
  K = K_;
  gr.assign(N, vector<tuple<int, int>>());
  pval.resize(N);
  qval.resize(N);
  inxy.assign(N, false);
  parent.resize(N);

  for (int i = 0; i < static_cast<int>(U.size()); i++) {
    gr[U[i]].emplace_back(V[i], W[i]);
    gr[V[i]].emplace_back(U[i], W[i]);
  }
  dfs(-1, X, 0, pval);
  dfs(-1, Y, 0, qval);
  for (int i = 0; i < N; i++) {
    auto t = min(pval[i], qval[i]);
    qval[i] = max(pval[i], qval[i]);
    pval[i] = t;
  }

  for (int u = X; u != -1; u = parent[u]) inxy[u] = true;
  return max(GetScoreWithCommon(), GetScoreWithoutCommon());
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17