Submission #857130

#	Time	Username	Problem	Language	Result	Execution time	Memory
857130		tvladm2009	Two Currencies (JOI23_currencies)	C++17	100 / 100	2704 ms	275948 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int 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;
int sub[N];
pair<int, int> updates[N];

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]];
  }
  sub[a] = 1;
  for (auto &b : g[a]) {
    if (b != p) {
      par[b] = a;
      dep[b] = dep[a] + 1;
      build(b, a);
      sub[a] += sub[b];
    }
  }
  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];
}

struct PST{
  struct Node {
    int result;
    Node* left;
    Node* right;

    Node (int val = 0) {
      result = val;
      left = right = nullptr;
    }

    void refresh() {
      this->result = this->left->result + this->right->result;
    }
  };

  Node* build(int from, int to) {
    Node *node = new Node(0);
    if (from < to) {
      int mid = (from + to) / 2;
      node->left = build(from, mid);
      node->right = build(mid + 1, to);
    }
    return node;
  }

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


  Node* update(Node* base, int from, int to, int x, int val) {
    if (from < to) {
      int mid = (from + to) / 2;
      Node* newNode = new Node();
      (*newNode) = (*base);
      if (x <= mid) {
        newNode->left = update(base->left, from, mid, x, val);
      } else {
        newNode->right = update(base->right, mid + 1, to, x, val);
      }
      newNode->refresh();
      return newNode;
    } else {
      return (new Node(base->result + val));
    }
  }

  int query(Node* node, int from, int to, int x, int y) {
    assert(from <= x && x <= y && y <= to);
    if (from == x && to == y) {
      return node->result;
    } else {
      int mid = (from + to) / 2;
      if (x <= mid && y <= mid) {
        return query(node->left, from, mid, x, y);
      } else if (mid + 1 <= x && mid + 1 <= y) {
        return query(node->right, mid + 1, to, x, y);
      } else {
        return query(node->left, from, mid,x , mid) + query(node->right, mid + 1, to, mid + 1, y);
      }
    }
  }

  Node* version[N];
  int n;

  void buildVersions(int n_) {
    n = n_;
    Node* part = initialize(n);
    version[0] = part;
    for(int i = 1; i <= m; i++) {
      int val = updates[i].first;
      int x = updates[i].second;
      part = update(part, 1, n, l[x], +val);
      if (r[x] + 1 <= n) {
        part = update(part, 1, n, r[x] + 1, -val);
      }
      version[i] = part;
    }
  }

  int sum(int when, int x) {
    return query(version[when], 1, n, 1, l[x]);
  }

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

PST tree1, tree2;

signed 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);

  tree1.buildVersions(n);
  for (int i = 1; i <= m; i++) {
    updates[i].first = 1;
  }
  tree2.buildVersions(n);


  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 (tree1.get_sum(mid, s, t) <= y) {
        sol = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    int z = lca(s, t);
    int payed = tree2.get_sum(sol, s, t);
    int total = tree2.get_sum(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:206:9: warning: unused variable 'z' [-Wunused-variable]
  206 |     int z = lca(s, t);
      |         ^

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