Submission #964145

#	Time	Username	Problem	Language	Result	Execution time	Memory
964145		happybelly	Closing Time (IOI23_closing)	C++17	100 / 100	338 ms	69692 KiB

closing

#include "closing.h"

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

struct Fenwick {
  vector<long long> a;

  int size;
  int lg;

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

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

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

  int lower_bound(long long v) {
    int idx = 0;
    long long 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<long long> pval, qval;
vector<vector<tuple<int, int>>> gr;
vector<bool> pxy;

int N;
long long K;

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

int GetScoreWithoutCommon() {
  vector<long long> pq;
  pq.insert(pq.end(), pval.begin(), pval.end());
  pq.insert(pq.end(), qval.begin(), qval.end());
  sort(pq.begin(), pq.end());
  long long total = 0;
  int ans = 0;
  for (long long c : pq) {
    if (total + c <= K) {
      total += c;
      ans++;
    }
  }
  return ans;
}

int GetScoreWithCommon() {
  vector<tuple<long long, 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 < static_cast<int>(elem.size()); i++) {
    int j = get<2>(elem[i]);
    if (get<1>(elem[i]) >= 0)
      pidx[j] = i;
    else
      qidx[j] = i;
  }

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

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

  auto GetOptimalLeftOver = [&](long long left) -> int {
    int idx = prefix.lower_bound(left + 1) - 1;
    long long 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]) <= left)
        return score;
    }

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

  long long total_xy = 0;
  int score_xy = 0, ans = 0;
  for (int i = 0; i < N; i++) {
    if (pxy[i]) {
      score_xy++;
      total_xy += pval[i];
      continue;
    }
    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]);
    if (pxy[node]) {
      total_xy += (qval[node] - pval[node]);
      score_xy++;
    } else {
      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 leftover = GetOptimalLeftOver(2 * (K - total_xy));
      ans = max(ans, score_xy + leftover);
    }
  }
  return ans;
}

int max_score(int _N, int X, int Y, long long _K, vector<int> U, vector<int> V,
              vector<int> W) {
  N = _N;
  K = _K;
  gr.assign(N, vector<tuple<int, int>>());
  pval.assign(N, 0);
  qval.assign(N, 0);
  pxy.assign(N, false);

  vector<int> parent(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, pval, parent);
  dfs(-1, Y, qval, parent);
  for (int i = 0; i < N; i++) {
    long long 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]) pxy[u] = true;
  return max(GetScoreWithoutCommon(), GetScoreWithCommon());
}

• 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