Editorial for Hai loại tiền tệ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Đối với bài toán này, mỗi truy vấn ta cần tìm số đồng vàng ít nhất cần phải sử dụng, hay nói cách khác cần tối đa hoá số trạm kiểm tra trên đường đi từ ~S_{i}~ đến ~T_{i}~ mà ta dùng đồng bạc để trả tiền. Cụ thể, ta cần tìm ~k~ lớn nhất sao cho tổng số đồng bạc phải trả trong ~k~ trạm nhỏ nhất trên đường từ ~S_{i}~ đến ~T_{i}~ không vượt quá ~Y_{i}~.

Ta có thể sử dụng chặt nhị phân song song (Parallel Binary Search) để giải quyết bài toán này. Đầu tiên sắp xếp các trạm kiểm tra theo số đồng bạc phải trả từ nhỏ đến lớn. Với mỗi lần duyệt, ta thêm dần các trạm kiểm tra và tính tổng trên đường đi từ ~S~ đến ~T~ để kiểm tra tổng có ~\le Y~ hay không. Việc tính tổng có thể thực hiện đơn giản với HLD hoặc Euler Tour.

Độ phức tạp: ~O(Q*log^{2}N)~.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
const int LOG = 18;
template <typename T>
struct binary_indexed_tree{
  int N;
  std::vector<T> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, T x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  T sum(int i){
    T ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
};
int main(){
  int N, M, Q;
  std::cin >> N >> M >> Q;
  std::vector<int> A(N - 1), B(N - 1);
  for (int i = 0; i < N - 1; i++){
    std::cin >> A[i] >> B[i];
    A[i]--;
    B[i]--;
  }
  std::vector<int> P(M), C(M);
  for (int i = 0; i < M; i++){
    std::cin >> P[i] >> C[i];
    P[i]--;
  }
  std::vector<int> S(Q), T(Q);
  std::vector<int> X(Q);
  std::vector<long long> Y(Q);
  for (int i = 0; i < Q; i++){
    std::cin >> S[i] >> T[i] >> X[i] >> Y[i];
    S[i]--;
    T[i]--;
  }
  std::vector<std::vector<int>> E(N);
  for (int i = 0; i < N - 1; i++){
    E[A[i]].push_back(B[i]);
    E[B[i]].push_back(A[i]);
  }
  std::vector<int> p(N, -1);
  std::vector<std::vector<int>> c(N);
  std::vector<int> d(N, 0);
  std::queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (int w : E[v]){
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        d[w] = d[v] + 1;
        q.push(w);
      }
    }
  }
  for (int i = 0; i < N - 1; i++){
    if (B[i] == p[A[i]]){
      std::swap(A[i], B[i]);
    }
  }
  std::vector<std::vector<int>> pp(LOG, std::vector<int>(N, -1));
  pp[0] = p;
  for (int i = 0; i < LOG - 1; i++){
    for (int j = 0; j < N; j++){
      if (pp[i][j] != -1){
        pp[i + 1][j] = pp[i][pp[i][j]];
      }
    }
  }
  std::vector<int> L(Q);
  for (int i = 0; i < Q; i++){
    int u = S[i], v = T[i];
    if (d[u] > d[v]){
      std::swap(u, v);
    }
    for (int j = 0; j < LOG; j++){
      if (((d[v] - d[u]) >> j & 1) == 1){
        v = pp[j][v];
      }
    }
    if (u == v){
      L[i] = u;
    } else {
      for (int j = LOG - 1; j >= 0; j--){
        if (pp[j][u] != pp[j][v]){
          u = pp[j][u];
          v = pp[j][v];
        }
      }
      L[i] = p[u];
    }
  }
  std::vector<int> in(N), out(N);
  int t = 0;
  auto dfs = [&](auto dfs, int v = 0) -> void {
    if (v != 0){
      in[v] = t;
      t++;
    }
    for (int w : c[v]){
      dfs(dfs, w);
    }
    if (v != 0){
      out[v] = t;
      t++;
    }
  };
  dfs(dfs);
  in[0] = -1;
  std::vector<std::pair<int, int>> D(M);
  for (int i = 0; i < M; i++){
    D[i] = std::make_pair(C[i], P[i]);
  }
  std::sort(D.begin(), D.end());
  std::vector<int> tv(Q, -1), fv(Q, M + 1);
  std::vector<int> cnt(Q);
  while (true){
    bool ok = true;
    std::vector<std::vector<int>> id(M + 1);
    for (int i = 0; i < Q; i++){
      if (fv[i] - tv[i] > 1){
        ok = false;
        id[(tv[i] + fv[i]) / 2].push_back(i);
      }
    }
    if (ok){
      break;
    }
    binary_indexed_tree<int> BIT1(N * 2 - 2);
    binary_indexed_tree<long long> BIT2(N * 2 - 2);
    for (int i = 0; i < M; i++){
      BIT1.add(in[B[P[i]]], 1);
      BIT1.add(out[B[P[i]]], -1);
    }
    for (int i = 0; i <= M; i++){
      for (int j : id[i]){
        long long s = BIT2.sum(in[S[j]] + 1) + BIT2.sum(in[T[j]] + 1) - BIT2.sum(in[L[j]] + 1) * 2;
        if (s <= Y[j]){
          cnt[j] = BIT1.sum(in[S[j]] + 1) + BIT1.sum(in[T[j]] + 1) - BIT1.sum(in[L[j]] + 1) * 2;
          tv[j] = i;
        } else {
          fv[j] = i;
        }
      }
      if (i < M){
        int x = D[i].first;
        int e = D[i].second;
        BIT1.add(in[B[e]], -1);
        BIT1.add(out[B[e]], 1);
        BIT2.add(in[B[e]], x);
        BIT2.add(out[B[e]], -x);
      }
    }
  }
  for (int i = 0; i < Q; i++){
    std::cout << std::max(X[i] - cnt[i], -1) << "\n";
  }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.