oj.uz

Submission #857129

# Submission time Handle Problem Language Result Execution time Memory
857129 2023-10-05T12:10:02 Z tvladm2009 Two Currencies (JOI23_currencies) C++17
10 / 100
 13 ms 4444 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
const int N = 2000 + 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 7 ms 3900 KB Output is correct
6 Correct 9 ms 3932 KB Output is correct
7 Correct 7 ms 3160 KB Output is correct
8 Correct 10 ms 4184 KB Output is correct
9 Correct 10 ms 4184 KB Output is correct
10 Correct 10 ms 4188 KB Output is correct
11 Correct 10 ms 4408 KB Output is correct
12 Correct 11 ms 4440 KB Output is correct
13 Correct 9 ms 3088 KB Output is correct
14 Correct 8 ms 3420 KB Output is correct
15 Correct 10 ms 3984 KB Output is correct
16 Correct 10 ms 4188 KB Output is correct
17 Correct 10 ms 4412 KB Output is correct
18 Correct 10 ms 4436 KB Output is correct
19 Correct 9 ms 4188 KB Output is correct
20 Correct 9 ms 4336 KB Output is correct
21 Correct 9 ms 4416 KB Output is correct
22 Correct 13 ms 4444 KB Output is correct
23 Correct 9 ms 4188 KB Output is correct
24 Correct 9 ms 4420 KB Output is correct
25 Correct 10 ms 4188 KB Output is correct
26 Correct 8 ms 4256 KB Output is correct
27 Correct 7 ms 4188 KB Output is correct
28 Correct 9 ms 4188 KB Output is correct
29 Correct 9 ms 4188 KB Output is correct
30 Correct 10 ms 4184 KB Output is correct
31 Correct 10 ms 4368 KB Output is correct
32 Correct 9 ms 4184 KB Output is correct
33 Correct 12 ms 3260 KB Output is correct
34 Correct 8 ms 2908 KB Output is correct
35 Correct 9 ms 3024 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 10 ms 4188 KB Output is correct
3 Correct 10 ms 4404 KB Output is correct
4 Correct 10 ms 4188 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 8 ms 2908 KB Output is correct
3 Correct 8 ms 2932 KB Output is correct
4 Correct 12 ms 3084 KB Output is correct
5 Runtime error 1 ms 860 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 7 ms 3900 KB Output is correct
6 Correct 9 ms 3932 KB Output is correct
7 Correct 7 ms 3160 KB Output is correct
8 Correct 10 ms 4184 KB Output is correct
9 Correct 10 ms 4184 KB Output is correct
10 Correct 10 ms 4188 KB Output is correct
11 Correct 10 ms 4408 KB Output is correct
12 Correct 11 ms 4440 KB Output is correct
13 Correct 9 ms 3088 KB Output is correct
14 Correct 8 ms 3420 KB Output is correct
15 Correct 10 ms 3984 KB Output is correct
16 Correct 10 ms 4188 KB Output is correct
17 Correct 10 ms 4412 KB Output is correct
18 Correct 10 ms 4436 KB Output is correct
19 Correct 9 ms 4188 KB Output is correct
20 Correct 9 ms 4336 KB Output is correct
21 Correct 9 ms 4416 KB Output is correct
22 Correct 13 ms 4444 KB Output is correct
23 Correct 9 ms 4188 KB Output is correct
24 Correct 9 ms 4420 KB Output is correct
25 Correct 10 ms 4188 KB Output is correct
26 Correct 8 ms 4256 KB Output is correct
27 Correct 7 ms 4188 KB Output is correct
28 Correct 9 ms 4188 KB Output is correct
29 Correct 9 ms 4188 KB Output is correct
30 Correct 10 ms 4184 KB Output is correct
31 Correct 10 ms 4368 KB Output is correct
32 Correct 9 ms 4184 KB Output is correct
33 Correct 12 ms 3260 KB Output is correct
34 Correct 8 ms 2908 KB Output is correct
35 Correct 9 ms 3024 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 10 ms 4188 KB Output is correct
38 Correct 10 ms 4404 KB Output is correct
39 Correct 10 ms 4188 KB Output is correct
40 Runtime error 1 ms 604 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -