oj.uz

Submission #795913

# Submission time Handle Problem Language Result Execution time Memory
795913 2023-07-27T21:48:59 Z erray Two Currencies (JOI23_currencies) C++17
30 / 100
 294 ms 41444 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] ? x :  y;
  }); 
  auto Lca = [&](int x, int y) {
    return (tout[x] >= tin[y] ? x : st.get(tout[x], tin[y]));   
  };
  auto Get = [&]<typename T>(int x, int y, Fenwick<T>& ft) -> T {
    debug(x, y, tout[x], tin[y], Lca(x, y));
    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) {
    debug(S[i], T[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 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 3 ms 980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 184 ms 38264 KB Output is correct
6 Correct 194 ms 37164 KB Output is correct
7 Correct 226 ms 28632 KB Output is correct
8 Correct 282 ms 41384 KB Output is correct
9 Correct 294 ms 40720 KB Output is correct
10 Correct 285 ms 41444 KB Output is correct
11 Correct 263 ms 41264 KB Output is correct
12 Correct 254 ms 40496 KB Output is correct
13 Correct 243 ms 40544 KB Output is correct
14 Correct 211 ms 39572 KB Output is correct
15 Correct 190 ms 39848 KB Output is correct
16 Correct 219 ms 39896 KB Output is correct
17 Correct 230 ms 40332 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 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 3 ms 980 KB Output isn't correct
6 Halted 0 ms 0 KB -