Submission #873842

#	Time	Username	Problem	Language	Result	Execution time	Memory
873842		LucaLucaM	Two Currencies (JOI23_currencies)	C++17	100 / 100	2503 ms	276904 KiB

currencies

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#define int long long // merg la comisie
#warning pica asta la jboi 1000%

/**

clar la fiecare query imi caut binar cati gold coins imi pot salva

cand avem query u--v :

fie c nr de checkpoint uri de pe lantul u--v

daca incerc sa iau k gold coins, trebuie sa vad care ar fi suma celor mai mici c - k valori de pe lantul u--v

ok deci am redus problema la

"raspunde la query uri de forma 'u v k' care este suma celor mai mici k valori de pe path-ul u--v"

pai hai sa imi sortez valorile crescator

dupa asta tot imi bag cate o muchie si o sa am ceva de genu
adauga muchia la toate nodurile din subarborele lui u (presupunem ca p[u] = v)

pai bun si acum am chestii de genu "adauga x la toate valorile dintr un range"

toate problemele se reduc la jmenul lui mars!!! (mi a soptit o pasarica)

**/

typedef long long ll;

const int NMAX = 1e5;
const int LGMAX = 17;

std::vector<int> g[NMAX + 1];
std::pair<int, int> edge[NMAX];
std::pair<int, int> checkpoint[NMAX + 1];

int tin[NMAX + 1], tout[NMAX + 1], timer;
int jump[LGMAX + 1][NMAX + 1];

void dfs(int u, int p = 0) {
  tin[u] = ++timer;
  jump[0][u] = p;
  for (const auto &v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
  tout[u] = timer;
}

bool ancestor(int u, int v) {
  return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

int lca(int u, int v) {
  if (ancestor(u, v)) {
    return u;
  }
  if (ancestor(v, u)) {
    return v;
  }
  for (int k = 16; k >= 0; k--) {
    if (jump[k][u] && !ancestor(jump[k][u], v)) {
      u = jump[k][u];
    }
  }
  return jump[0][u];
}

struct PST {
  struct Node {
    int res;
    Node *l, *r;

    Node(int value = 0) {
      res = value;
      l = r = NULL;
    }

    void refresh() {
      this -> res = this -> l -> res + this -> r -> res;
    }
  };

  Node* build(int tl, int tr) {
    Node* node = new Node(0);
    if (tl < tr) {
      int mid = (tl + tr) / 2;
      node -> l = build(tl, mid);
      node -> r = build(mid + 1, tr);
    }
    return node;
  }

  Node* init(int n) {
    return build(1, n);
  }

  Node* update(Node* base, int tl, int tr, int p, int val) {
    if (tl == tr) {
      return (new Node(base -> res + val));
    }
    int mid = (tl + tr) / 2;
    Node* ret = new Node();
    (*ret = *base);
    if (p <= mid) {
      ret -> l = update(base->l, tl, mid, p, val);
    } else {
      ret -> r = update(base->r, mid + 1, tr, p, val);
    }
    ret -> refresh();
    return ret;
  }

  int query(Node* node, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      return node -> res;
    }
    int mid = (tl + tr) / 2;
    if (l <= mid && mid < r) {
      return query(node -> l, tl, mid, l, r) + query(node -> r, mid + 1, tr, l, r);
    } else if (l <= mid) {
      return query(node -> l, tl, mid, l, r);
    } else {
      return query(node -> r, mid + 1, tr, l, r);
    }
  }

  Node* version[NMAX + 1];
  int n;

  void buildVersions(int _n, std::vector<std::tuple<int, int, int>> updates) {
    n = _n + 1;
    Node *cur = init(n);
    version[0] = cur;
    for (int i = 1; i <= (int) updates.size(); i++) {
      auto [add, l, r] = updates[i - 1];
      cur = update(cur, 1, n, l, +add);
      cur = update(cur, 1, n, r + 1, -add);
      version[i] = cur;
    }
  }

  int sum(int when, int x) {
    return query(version[when], 1, n, 1, tin[x]);
  }
  int get(int when, int u, int v) {
    int w = lca(u, v);
    return sum(when, u) + sum(when, v) - 2 * sum(when, w);
  }
};

PST cnt, sum;

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    edge[i] = {u, v};
    g[u].push_back(v);
    g[v].push_back(u);
  }

  dfs(1);

  for (int j = 1; j < 17; j++) {
    for (int i = 1; i <= n; i++) {
      jump[j][i] = jump[j - 1][jump[j - 1][i]];
    }
  }


  for (int i = 1; i < n; i++) {
    auto [u, v] = edge[i];
    if (tin[u] < tin[v]) { // p[v] = u
      /// AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
      std::swap(edge[i].first, edge[i].second); // acum p[u] = v
    }
  }

  std::vector<std::tuple<int, int, int>> updates;

  for (int i = 1; i <= m; i++) {
    int idx, c;
    std::cin >> idx >> c;
    auto [u, v] = edge[idx];
    updates.push_back({c, tin[u], tout[u]});
  }

  std::sort(updates.begin(), updates.end());

  sum.buildVersions(n, updates);

  for (auto &[c, l, r] : updates) {
    c = 1;
  }

  cnt.buildVersions(n, updates);

  while (q--) {
    int u, v, x, y;
    std::cin >> u >> v >> x >> y;
    int l = 1, r = m, sol = 0;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (sum.get(mid, u, v) <= y) {
        sol = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    int silver = cnt.get(sol, u, v);
    int answer = x - (cnt.get(m, u, v) - silver);
    if (answer < 0) {
      answer = -1;
    }
    std::cout << answer << '\n';
  }

  return 0;
}

Compilation message (stderr)

currencies.cpp:8:2: warning: #warning pica asta la jboi 1000% [-Wcpp]
    8 | #warning pica asta la jboi 1000%
      |  ^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32