oj.uz

Submission #795908

# Submission time Handle Problem Language Result Execution time Memory
795908 2023-07-27T21:38:50 Z erray Two Currencies (JOI23_currencies) C++17
30 / 100
 340 ms 47136 KB 
// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

template<typename T, typename F = function<T(const T&, const T&)>> 
struct SparseTable {
  vector<vector<T>> a;
  int n;
  F op;
  SparseTable() { }
  SparseTable(vector<T> _a, F _op) : op(_op) {
    n = int(_a.size());
    int lg = 32 - __builtin_clz(n);
    a.resize(lg); 
    a[0] = _a;
    for (int j = 1; j < lg; ++j) {
      int size = n - (1 << j) + 1;
      a[j].resize(size);
      for (int i = 0; i < size; ++i) {
        a[j][i] = op(a[j - 1][i], a[j - 1][i + ((1 << (j - 1)))]);
      }
    }
  }
  T get(int l, int r) {
    assert(l >= 0 && r < n && l <= r);
    int lg = __lg(r - l + 1);
    return op(a[lg][l], a[lg][r + 1 - (1 << lg)]);
  }
};

template<typename T>
struct Fenwick {
  vector<T> tree; 
  int n;
  Fenwick(int _n) : n(_n) {
    tree.resize(n + 1);
  }
  T get(int x) {
    x += 1;
    T res = 0;
    while (x > 0) {
      res += tree[x];
      x -= x & -x;
    }
    return res;
  }
  void modify(int x, T d) {
    x += 1;
    while (x <= n) {
      tree[x] += d;
      x += x & -x;  
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<int> A(N - 1), B(N - 1);
  vector<vector<int>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    cin >> A[i] >> B[i];
    --A[i], --B[i];
    g[A[i]].push_back(i);
    g[B[i]].push_back(i);
  }
  vector<array<int, 2>> C(M);
  for (int i = 0; i < M; ++i) {
    cin >> C[i][1] >> C[i][0];
    --C[i][1];
  } 
  sort(C.begin(), C.end());
  vector<int> S(Q), T(Q), X(Q);
  vector<long long> Y(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> S[i] >> T[i] >> X[i] >> Y[i];
    --S[i], --T[i];
  }
  vector<int> tin(N), tout(N), d(N), tour;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    tin[v] = int(tour.size());
    tour.push_back(v);
    bool leaf = true;
    for (auto id : g[v]) {
      int u = A[id] ^ B[id] ^ v;
      if (u == pr) {
        continue;
      }
      if (A[id] == u) {
        swap(A[id], B[id]);
      }
      d[u] = d[v] + 1;
      Dfs(u, v);
      tout[v] = int(tour.size());
      tour.push_back(v);
      leaf = false;
    }
    if (leaf) {      
      tout[v] = int(tour.size());
      tour.push_back(v);
    }
  };
  Dfs(0, -1);
  debug(d, tour, tin, tout);
  int s = int(tour.size());
  for (int i = 0; i < Q; ++i) {
    if (tin[S[i]] > tin[T[i]]) {
      swap(S[i], T[i]);
    }
  }                    
  for (int i = 0; i < M; ++i) {
    C[i][1] = B[C[i][1]];
  }
  SparseTable st(tour, [&](int x, int y) {
    return d[x] < d[y];
  }); 
  auto Lca = [&](int x, int y) {
    return (tout[x] >= tout[y] ? x : st.get(tout[x], tin[y]));   
  };
  auto Get = [&]<typename T>(int x, int y, Fenwick<T>& ft) -> T {
    return ft.get(tin[x]) + ft.get(tin[y]) - 2 * ft.get(Lca(x, y));
  };
  auto Modify = [&]<typename T>(int x, int delta, Fenwick<T>& ft) {
    ft.modify(tin[x], delta);  
    ft.modify(tout[x], -delta);  
  };

  debug(C); 
  Fenwick<long long> sum(s);
  int p = 0;
  vector<vector<int>> point(M + 1);
  function<void(vector<int>, int l, int r)> Pbs = [&](vector<int> qs, int l, int r) {
    if (l == r) {
      point[l] = qs;
      return;   
    }
    debug(l, r, qs);
    int mid = 1 + ((l + r) >> 1);
    while (p < mid) {
      Modify(C[p][1], C[p][0], sum);
      ++p;
    }
    while (mid < p) {
      --p;
      Modify(C[p][1], -C[p][0], sum);
    }
    vector<int> left, right;
    for (auto i : qs) {
      (Get(S[i], T[i], sum) > Y[i] ? left : right).push_back(i);
    }
    Pbs(left, l, mid - 1);
    Pbs(right, mid, r);
  };
  vector<int> foo(Q);
  iota(foo.begin(), foo.end(), 0);
  Pbs(foo, 0, M); 
  debug(point);
  Fenwick<int> cnt(s);
  for (int i = 0; i <= M; ++i) {
    for (auto id : point[i]) {
      X[id] += Get(S[id], T[id], cnt);
    }
    if (i < M) {
      Modify(C[i][1], +1, cnt); 
    }   
  }
  debug(X);
  for (int i = 0; i < Q; ++i) {
    X[i] -= Get(S[i], T[i], cnt);
  }
  for (int i = 0; i < Q; ++i) {
    cout << max(X[i], -1) << '\n';
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 1108 KB Output is correct
3 Correct 4 ms 1108 KB Output is correct
4 Correct 5 ms 1108 KB Output is correct
5 Correct 203 ms 42432 KB Output is correct
6 Correct 186 ms 41308 KB Output is correct
7 Correct 237 ms 33580 KB Output is correct
8 Correct 340 ms 47136 KB Output is correct
9 Correct 293 ms 46456 KB Output is correct
10 Correct 297 ms 47100 KB Output is correct
11 Correct 257 ms 47012 KB Output is correct
12 Correct 263 ms 46276 KB Output is correct
13 Correct 245 ms 46364 KB Output is correct
14 Correct 227 ms 45104 KB Output is correct
15 Correct 189 ms 45440 KB Output is correct
16 Correct 222 ms 45616 KB Output is correct
17 Correct 228 ms 45976 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 320 KB Output isn't correct
3 Halted 0 ms 0 KB -