oj.uz

Submission #855787

# Submission time Handle Problem Language Result Execution time Memory
855787 2023-10-01T19:25:55 Z tvladm2009 Two Currencies (JOI23_currencies) C++17
10 / 100
 5000 ms 705680 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 7;
const int K = 20;
const int B = 317;
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];
ll sumToRoot[B][N];
ll prefSum[B][N];
int countToRoot[B][N];
int prefCount[B][N];

int get_bucket(int x) {
  return (x - 1) / B + 1;
}

struct segtree {
  int n;
  vector<ll> tree;
  vector<ll> lazy;

  void init(int nn) {
    n = nn;
    tree.resize(4 * n + 1);
    lazy.resize(4 * n + 1);
    for (int i = 1; i <= 4 * n; i++) {
      tree[i] = 0;
      lazy[i] = 0;
    }
  }

  void push(int v, int tl, int tr) {
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    tree[v] += lazy[v];
    lazy[v] = 0;
  }

  void applyRange(int v, int tl, int tr, int x, int y, ll val) {
    push(v, tl, tr);
    if (x <= tl && tr <= y) {
      lazy[v] += val;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    if (x <= tm) {
      applyRange(2 * v, tl, tm, x, min(tm, y), val);
    }
    if (tm + 1 <= y) {
      applyRange(2 * v + 1, tm + 1, tr, max(x, tm + 1), y, val);
    }
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
  }

  ll force(int v, int tl, int tr, int x, int y) {
    push(v, tl, tr);
    if (x <= tl && tr <= y) {
      return tree[v];
    }
    int tm = (tl + tr) / 2;
    if (x <= tm && y <= tm) {
      return force(2 * v, tl, tm, x, y);
    } else if (tm + 1 <= x && tm + 1 <= y) {
      return force(2 * v + 1, tm + 1, tr, x, y);
    } else {
      return force(2 * v, tl, tm, x, tm) + force(2 * v + 1, tm + 1, tr, tm + 1, tr);
    }
  }
};

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) {
  return l[x] <= l[y] && r[y] <= r[x];
}

ll getToRoot(int when, int node) {
  if (node == 0) {
    return 0;
  }
  int bucket = get_bucket(when) - 1;
  ll sol = prefSum[bucket][node];
  for (int i = B * bucket + 1; i <= when; i++) {
    ll val = updates[i].first;
    int x = updates[i].second;
    if (is_ancestor(x, node)) {
      sol += val;
    }
  }
  return sol;
}

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

ll getToRoot2(int when, int node) {
  if (node == 0) {
    return 0;
  }
  int bucket = get_bucket(when) - 1;
  ll sol = prefCount[bucket][node];
  for (int i = B * bucket + 1; i <= when; i++) {
    int x = updates[i].second;
    if (is_ancestor(x, node)) {
      sol++;
    }
  }
  return sol;
}

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

struct T {
  int s;
  int t;
  int x;
  ll y;
  int low;
  int high;
  int mid;
  int sol;
  int id;
};

vector<T> queries;
int moment[N];
int print[N];

void get_moments() {
  int mm = m;
  while (m > 0) {
    m /= 2;
    int k = 0;
    vector<T> new_queries, others;
    while (k < (int) queries.size()) {
      ll now = get_sum(queries[k].mid, queries[k].s, queries[k].t);
      if (now <= queries[k].y) {
        queries[k].sol = queries[k].mid;
        queries[k].low = queries[k].mid + 1;
        queries[k].mid = (queries[k].low + queries[k].high) / 2;
        others.push_back(queries[k]);
      } else {
        queries[k].high = queries[k].mid;
        queries[k].mid = (queries[k].low + queries[k].high) / 2;
        new_queries.push_back(queries[k]);
      }
      k++;
    }
    for (auto &it : others) {
      new_queries.push_back(it);
    }
    others.clear();
    queries = new_queries;
  }
  m = mm;
}

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
    for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
      segtree tree;
      tree.init(n);
      for (int i = (bucket - 1) * B + 1; i <= bucket * B; i++) {
        ll val = updates[i].first;
        int x = updates[i].second;
        if (x != 0) {
          tree.applyRange(1, 1, n, l[x], r[x], val);
        }
      }
      for (int i = 1; i <= n; i++) {
        sumToRoot[bucket][i] = tree.force(1, 1, n, l[i], l[i]);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
        prefSum[bucket][i] = prefSum[bucket - 1][i] + sumToRoot[bucket][i];
      }
    }
  }
  { /// for cnt
    for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
      segtree tree;
      tree.init(n);
      for (int i = (bucket - 1) * B + 1; i <= bucket * B; i++) {
        int x = updates[i].second;
        if (x != 0) {
          tree.applyRange(1, 1, n, l[x], r[x], 1);
        }
      }
      for (int i = 1; i <= n; i++) {
        countToRoot[bucket][i] = tree.force(1, 1, n, l[i], l[i]);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int bucket = 1; bucket <= get_bucket(m); bucket++) {
        prefCount[bucket][i] = prefCount[bucket - 1][i] + countToRoot[bucket][i];
      }
    }
  }

  for (int i = 0; i < q; i++) {
    T aux;
    cin >> aux.s >> aux.t >> aux.x >> aux.y;
    aux.low = 1;
    aux.high = m;
    aux.mid = (m + 1) / 2;
    aux.sol = 0;
    aux.id = i + 1;
    queries.push_back(aux);
  }
  get_moments();
  for (int iq = 0; iq < q; iq++) {
    int s = queries[iq].s;
    int t = queries[iq].t;
    int x = queries[iq].x;
    ll y = queries[iq].y;

    int sol = queries[iq].sol;
    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;
    }
    print[queries[iq].id] = keep;
  }
  for (int i = 1; i <= q; i++) {
    cout << print[i] << "\n";
  }
  return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:300:8: warning: unused variable 'y' [-Wunused-variable]
  300 |     ll y = queries[iq].y;
      |        ^
currencies.cpp:303:9: warning: unused variable 'z' [-Wunused-variable]
  303 |     int z = lca(s, t);
      |         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 26 ms 30832 KB Output is correct
6 Correct 35 ms 31012 KB Output is correct
7 Correct 28 ms 31008 KB Output is correct
8 Correct 35 ms 33096 KB Output is correct
9 Correct 33 ms 33100 KB Output is correct
10 Correct 35 ms 33100 KB Output is correct
11 Correct 36 ms 33056 KB Output is correct
12 Correct 38 ms 33060 KB Output is correct
13 Correct 38 ms 33192 KB Output is correct
14 Correct 48 ms 33116 KB Output is correct
15 Correct 43 ms 33112 KB Output is correct
16 Correct 44 ms 33064 KB Output is correct
17 Correct 45 ms 33048 KB Output is correct
18 Correct 42 ms 33076 KB Output is correct
19 Correct 30 ms 33072 KB Output is correct
20 Correct 33 ms 33064 KB Output is correct
21 Correct 31 ms 33128 KB Output is correct
22 Correct 30 ms 33080 KB Output is correct
23 Correct 28 ms 33328 KB Output is correct
24 Correct 33 ms 33348 KB Output is correct
25 Correct 31 ms 33132 KB Output is correct
26 Correct 25 ms 33044 KB Output is correct
27 Correct 19 ms 33080 KB Output is correct
28 Correct 23 ms 33092 KB Output is correct
29 Correct 23 ms 33092 KB Output is correct
30 Correct 34 ms 33008 KB Output is correct
31 Correct 32 ms 33056 KB Output is correct
32 Correct 30 ms 33072 KB Output is correct
33 Correct 35 ms 33144 KB Output is correct
34 Correct 36 ms 33160 KB Output is correct
35 Correct 36 ms 33120 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 33 ms 32996 KB Output is correct
3 Correct 35 ms 33056 KB Output is correct
4 Correct 30 ms 33068 KB Output is correct
5 Execution timed out 5080 ms 529376 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 36 ms 33052 KB Output is correct
3 Correct 36 ms 33172 KB Output is correct
4 Correct 35 ms 33152 KB Output is correct
5 Correct 4673 ms 525976 KB Output is correct
6 Correct 3947 ms 433812 KB Output is correct
7 Correct 4643 ms 705680 KB Output is correct
8 Execution timed out 5036 ms 670020 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 26 ms 30832 KB Output is correct
6 Correct 35 ms 31012 KB Output is correct
7 Correct 28 ms 31008 KB Output is correct
8 Correct 35 ms 33096 KB Output is correct
9 Correct 33 ms 33100 KB Output is correct
10 Correct 35 ms 33100 KB Output is correct
11 Correct 36 ms 33056 KB Output is correct
12 Correct 38 ms 33060 KB Output is correct
13 Correct 38 ms 33192 KB Output is correct
14 Correct 48 ms 33116 KB Output is correct
15 Correct 43 ms 33112 KB Output is correct
16 Correct 44 ms 33064 KB Output is correct
17 Correct 45 ms 33048 KB Output is correct
18 Correct 42 ms 33076 KB Output is correct
19 Correct 30 ms 33072 KB Output is correct
20 Correct 33 ms 33064 KB Output is correct
21 Correct 31 ms 33128 KB Output is correct
22 Correct 30 ms 33080 KB Output is correct
23 Correct 28 ms 33328 KB Output is correct
24 Correct 33 ms 33348 KB Output is correct
25 Correct 31 ms 33132 KB Output is correct
26 Correct 25 ms 33044 KB Output is correct
27 Correct 19 ms 33080 KB Output is correct
28 Correct 23 ms 33092 KB Output is correct
29 Correct 23 ms 33092 KB Output is correct
30 Correct 34 ms 33008 KB Output is correct
31 Correct 32 ms 33056 KB Output is correct
32 Correct 30 ms 33072 KB Output is correct
33 Correct 35 ms 33144 KB Output is correct
34 Correct 36 ms 33160 KB Output is correct
35 Correct 36 ms 33120 KB Output is correct
36 Correct 3 ms 18012 KB Output is correct
37 Correct 33 ms 32996 KB Output is correct
38 Correct 35 ms 33056 KB Output is correct
39 Correct 30 ms 33068 KB Output is correct
40 Execution timed out 5080 ms 529376 KB Time limit exceeded
41 Halted 0 ms 0 KB -