Submission #855805

#	Time	Username	Problem	Language	Result	Execution time	Memory
855805		tvladm2009	Two Currencies (JOI23_currencies)	C++17	0 / 100	2 ms	13148 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 7;
const int K = 20;
int n;
int m;
int q;
vector<int> g[N];
pair<int, int> edges[N];
int dep[N];
int par[N];
int l[N];
int r[N];
int tab[K][N];
int tt = 0;
pair<int, int> updates[N];

struct Node {
  Node* l;
  Node* r;
  int sum;
  int lazy;

  Node(Node* ll = NULL, Node *rr = NULL, int ssum = 0, int llazy = 0) {
    l = ll;
    r = rr;
    sum = ssum;
    lazy = llazy;
  }
};

Node* sum[N];
Node* cnt[N];

void push(Node* &root, int tl, int tr) {
  assert(root != NULL);
  if (tl < tr) {
    assert(root->l != NULL);
    assert(root->r != NULL);
    root->l = new Node(root->l->l, root->l->r, root->l->sum, root->l->lazy + root->lazy);
    root->r = new Node(root->r->l, root->r->r, root->r->sum, root->r->lazy + root->lazy);
  }
  root = new Node(root->l, root->r, root->sum + root->lazy, 0);
}

void build(Node* &root, int tl, int tr) {
  root = new Node();
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    build(root->l, tl, tm);
    build(root->r, tm + 1, tr);
  }
}

void print(Node* root, int v = 1) {
  cout << v << "\n";
  if (root->l != NULL) {
    print(root->l, 2 * v);
  }
  if (root->r != NULL) {
    print(root->r, 2 * v + 1);
  }
}

void update(Node* &root, Node* old, int tl, int tr, int x, int y, int val) {
  root = old;
  push(root, tl, tr);
  if (x <= tl && tr <= y) {
    root->lazy += val;
    push(root, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  if (x <= tm && y <= tm) {
    root->r = old->r;
    update(root->l, old->l, tl, tm, x, y, val);
  } else if (tm + 1 <= x && tm + 1 <= y) {
    root->l = old->l;
    update(root->r, old->r, tm + 1, tr, x, y, val);
  } else {
    update(root->l, old->l, tl, tm, x, tm, val);
    update(root->r, old->r, tm + 1, tr, tm + 1, y, val);
  }
  push(root->l, tl, tm);
  push(root->r, tm + 1, tr);
  root->sum = root->l->sum + root->r->sum;
}

int query(Node* &root, int tl, int tr, int x, int y) {
  push(root, tl, tr);
  if (x <= tl && tr <= y) {
    return root->sum;
  }
  int tm = (tl + tr) / 2;
  if (x <= tm && y <= tm) {
    return query(root->l, tl, tm, x, y);
  } else if (tm + 1 <= x && tm + 1 <= y) {
    return query(root->r, tm + 1, tr, x, y);
  } else {
    return query(root->l, tl, tm, x, tm) + query(root->r, tm + 1, tr, tm + 1, y);
  }
}

int get(Node* root, int x) {
  return query(root, 1, n, l[x], l[x]);
}

void build(int a, int p = 0) {
  l[a] = ++tt;
  tab[0][a] = p;
  for (int k = 1; k < K; k++) {
    tab[k][a] = tab[k - 1][tab[k - 1][a]];
  }
  for (auto &b : g[a]) {
    if (b != p) {
      par[b] = a;
      dep[b] = dep[a] + 1;
      build(b, a);
    }
  }
  r[a] = tt;
}

int lca(int x, int y) {
  if (dep[x] < dep[y]) {
    swap(x, y);
  }
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[y]) {
      x = tab[k][x];
    }
  }
  if (x == y) {
    return x;
  }
  for (int k = K - 1; k >= 0; k--) {
    if (tab[k][x] != tab[k][y]) {
      x = tab[k][x];
      y = tab[k][y];
    }
  }
  return tab[0][x];
}

bool is_ancestor(int x, int y) { /// x ancestor of y
  return l[x] <= l[y] && r[y] <= r[x];
}

ll get_sum(int when, int x, int y) {
  int z = lca(x, y);
  return get(sum[when], x) + get(sum[when], y) - 2 * get(sum[when], z);
}

ll get_count(int when, int x, int y) {
  int z = lca(x, y);
  return get(cnt[when], x) + get(cnt[when], y) - 2 * get(cnt[when], z);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 /// freopen("input.txt", "r", stdin);

  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
    edges[i] = {x, y};
  }
  build(1);
  for (int i = 1; i <= m; i++) {
    ll road, val;
    cin >> road >> val;
    int x = edges[road].first;
    int y = edges[road].second;
    if (dep[x] < dep[y]) {
      swap(x, y);
    }
    updates[i] = {val, x};
  }
  sort(updates + 1, updates + m + 1);


  { /// for sum
    Node* root = new Node();
    build(root, 1, n);
    /// print(root);
    sum[0] = root;
    for (int i = 1; i <= m; i++) {
      int val = updates[i].first;
      int x = updates[i].second;
      sum[i] = root;
      update(sum[i], root, 1, n, l[x], r[x], val);
      root = sum[i];
    }
  }
  { /// for cnt
    Node* root = new Node();
    build(root, 1, n);
    cnt[0] = root;
    for (int i = 1; i <= m; i++) {
      int val = updates[i].first;
      int x = updates[i].second;
      cnt[i] = root;
      update(cnt[i], root, 1, n, l[x], r[x], 1);
      root = cnt[i];
    }
  }

  while (q--) {
    ll s, t, x, y;
    cin >> s >> t >> x >> y;
    int low = 1, high = m, sol = 0;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (get_sum(mid, s, t) <= y) {
        sol = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    int z = lca(s, t);
    int payed = get_count(sol, s, t);
    int total = get_count(m, s, t);
    int keep = x - (total - payed);
    if (keep < 0) {
      keep = -1;
    }
    cout << keep << "\n";
  }
  return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:207:11: warning: unused variable 'val' [-Wunused-variable]
  207 |       int val = updates[i].first;
      |           ^~~
currencies.cpp:228:9: warning: unused variable 'z' [-Wunused-variable]
  228 |     int z = lca(s, t);
      |         ^

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