Submission #964035

#	Time	Username	Problem	Language	Result	Execution time	Memory
964035		happybelly	Closing Time (IOI23_closing)	C++17	0 / 100	1129 ms	1324764 KiB

closing

#include "closing.h"

#include <algorithm>
#include <vector>

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, int 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(int v) {
    int idx = 0;
    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;

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

int GetScoreWithoutCommon(int K) {
  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());
  return lower_bound(pq.begin(), pq.end(), K + 1) - pq.begin();
}

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

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

    int curr_p = p_ctr.lower_bound(p_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, std::vector<int> U,
              std::vector<int> V, std::vector<int> W) {
  gr.resize(N);
  pval.resize(N);
  qval.resize(N);
  pxy.resize(N);

  vector<int> parent(N);
  for (int i = 0; i < U.size(); i++) {
    gr[U[i]].push_back(make_tuple(V[i], W[i]));
    gr[V[i]].push_back(make_tuple(U[i], W[i]));
  }
  dfs(-1, X, 0, pval, parent);
  dfs(-1, Y, 0, qval, parent);
  for (int i = 0; i < N; i++) {
    int 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(K), GetScoreWithCommon(N, K));
}

Compilation message (stderr)

closing.cpp: In function 'int GetScoreWithCommon(int, int)':
closing.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i = 0; i < elem.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:154:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for (int i = 0; i < U.size(); i++) {
      |                   ~~^~~~~~~~~~

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