oj.uz

Submission #966068

# Submission time Handle Problem Language Result Execution time Memory
966068 2024-04-19T10:34:53 Z NeroZein Two Currencies (JOI23_currencies) C++17
10 / 100
 143 ms 138396 KB 
#include "bits/stdc++.h"
using namespace std;
 
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
 
const int LOG = 17;
const int N = 1e5 + 5;
const int M = 1e9 + 2;
 
int n, m, q;
vector<int> g[N];
pair<int, int> edge[N];
pair<int, int> checkpoint[N];
 
int idd; 
int dep[N], up[LOG][N];
 
vector<int> vec[N];
pair<long long, int> tr[N * LOG];
int rt[N], lc[N * LOG * 2], rc[N * LOG * 2];
 
void dfs(int v, int p) {
  for (int u : g[v]) {
    if (u == p) continue; 
    dep[u] = dep[v] + 1; 
    up[0][u] = v;
    for (int j = 1; j < LOG; ++j) {
      up[j][u] = up[j - 1][up[j - 1][u]];
    }
    dfs(u, v);
  }
}
 
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = up[j][u];
    }
  }
  if (u == v) return v;
  for (int j = LOG - 1; j >= 0; --j) {
    if (up[j][u] != up[j][v]) {
      u = up[j][u]; v = up[j][v];
    }
  }
  return up[0][v];
}
 
pair<long long, int> comb(pair<long long, int> x, pair<long long, int> y) {
  x.first += y.first;
  x.second += y.second;
  return x; 
}
 
int upd(int nd, int l, int r, int p) {
  int nx = ++idd;
  if (l == r) {
    tr[nx] = comb(tr[nd], make_pair(p, 1));
    return nx; 
  }
  int mid = (l + r) / 2;
  if (p <= mid) {
    rc[nx] = rc[nd];
    lc[nx] = upd(lc[nd], l, mid, p);
  } else {
    lc[nx] = lc[nd];
    rc[nx] = upd(rc[nd], mid + 1, r, p);
  }
  tr[nx] = comb(tr[lc[nx]], tr[rc[nx]]);
  return nx; 
}
 
pair<long long, int> get(pair<long long, int> x, pair<long long, int> y, pair<long long, int> z) {
  pair<long long, int> ret;
  ret.first = x.first + y.first - 2 * z.first;
  ret.second = x.second + y.second - 2 * z.second;
  return ret;
}
 
int dive(int nd1, int nd2, int nd3, int l, int r, long long k) {
  if (l == r) {
    auto p = get(tr[nd1], tr[nd2], tr[nd3]);
    return p.second - min((long long) p.second, k / l);
  }
  int ret = 0;
  int mid = (l + r) / 2; 
  auto p = get(tr[lc[nd1]], tr[lc[nd2]], tr[lc[nd3]]);
  if (p.first >= k) {
    ret = tr[rc[nd1]].second + tr[rc[nd2]].second - 2 * tr[rc[nd3]].second;
    ret += dive(lc[nd1], lc[nd2], lc[nd3], l, mid, k);
  } else {
    ret = dive(rc[nd1], rc[nd2], rc[nd3], mid + 1, r, k - p.first);    
  }
  return ret;
}
 
void dfs2(int v, int p) {
  for (int u : g[v]) {
    if (u == p) {
      continue; 
    }
    rt[u] = rt[v];
    for (int j : vec[u]) {
      rt[u] = upd(rt[u], 1, M, j);
    }
    dfs2(u, v);
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> q;
  for(int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    edge[i] = {u, v};
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> checkpoint[i].first >> checkpoint[i].second;
  }
  dfs(1, 0);
  for (int i = 1; i < n; ++i) {
    if (dep[edge[i].first] > dep[edge[i].second]) {
      swap(edge[i].first, edge[i].second);
    }
  }
  for (int i = 1; i <= m; ++i) {
    vec[edge[checkpoint[i].first].second].push_back(checkpoint[i].second);
  }
  dfs2(1, 0);
  while (q--) {
    int u, v, gold;
    long long silver;
    cin >> u >> v >> gold >> silver; 
    int ca = lca(u, v);
    int used = dive(rt[u], rt[v], rt[ca], 1, M, silver); 
    cout << max(gold - used, -1) << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13660 KB Output is correct
2 Correct 2 ms 13660 KB Output is correct
3 Correct 3 ms 13660 KB Output is correct
4 Correct 2 ms 13660 KB Output is correct
5 Correct 5 ms 17244 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 5 ms 14940 KB Output is correct
8 Correct 8 ms 17252 KB Output is correct
9 Correct 6 ms 17252 KB Output is correct
10 Correct 6 ms 17240 KB Output is correct
11 Correct 7 ms 17244 KB Output is correct
12 Correct 6 ms 17244 KB Output is correct
13 Correct 7 ms 17568 KB Output is correct
14 Correct 7 ms 17500 KB Output is correct
15 Correct 7 ms 17496 KB Output is correct
16 Correct 7 ms 17244 KB Output is correct
17 Correct 6 ms 17244 KB Output is correct
18 Correct 7 ms 17244 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17316 KB Output is correct
21 Correct 6 ms 17244 KB Output is correct
22 Correct 6 ms 17240 KB Output is correct
23 Correct 6 ms 17496 KB Output is correct
24 Correct 6 ms 17244 KB Output is correct
25 Correct 6 ms 17244 KB Output is correct
26 Correct 5 ms 17244 KB Output is correct
27 Correct 6 ms 17244 KB Output is correct
28 Correct 6 ms 17248 KB Output is correct
29 Correct 7 ms 17244 KB Output is correct
30 Correct 6 ms 17240 KB Output is correct
31 Correct 6 ms 17244 KB Output is correct
32 Correct 6 ms 17244 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 7 ms 17500 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 6 ms 17244 KB Output is correct
3 Correct 6 ms 17280 KB Output is correct
4 Correct 6 ms 17244 KB Output is correct
5 Runtime error 130 ms 124500 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 2 ms 13656 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 17500 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Runtime error 143 ms 138396 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 2 ms 13660 KB Output is correct
2 Correct 2 ms 13660 KB Output is correct
3 Correct 3 ms 13660 KB Output is correct
4 Correct 2 ms 13660 KB Output is correct
5 Correct 5 ms 17244 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 5 ms 14940 KB Output is correct
8 Correct 8 ms 17252 KB Output is correct
9 Correct 6 ms 17252 KB Output is correct
10 Correct 6 ms 17240 KB Output is correct
11 Correct 7 ms 17244 KB Output is correct
12 Correct 6 ms 17244 KB Output is correct
13 Correct 7 ms 17568 KB Output is correct
14 Correct 7 ms 17500 KB Output is correct
15 Correct 7 ms 17496 KB Output is correct
16 Correct 7 ms 17244 KB Output is correct
17 Correct 6 ms 17244 KB Output is correct
18 Correct 7 ms 17244 KB Output is correct
19 Correct 6 ms 17244 KB Output is correct
20 Correct 6 ms 17316 KB Output is correct
21 Correct 6 ms 17244 KB Output is correct
22 Correct 6 ms 17240 KB Output is correct
23 Correct 6 ms 17496 KB Output is correct
24 Correct 6 ms 17244 KB Output is correct
25 Correct 6 ms 17244 KB Output is correct
26 Correct 5 ms 17244 KB Output is correct
27 Correct 6 ms 17244 KB Output is correct
28 Correct 6 ms 17248 KB Output is correct
29 Correct 7 ms 17244 KB Output is correct
30 Correct 6 ms 17240 KB Output is correct
31 Correct 6 ms 17244 KB Output is correct
32 Correct 6 ms 17244 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 7 ms 17500 KB Output is correct
36 Correct 3 ms 13660 KB Output is correct
37 Correct 6 ms 17244 KB Output is correct
38 Correct 6 ms 17280 KB Output is correct
39 Correct 6 ms 17244 KB Output is correct
40 Runtime error 130 ms 124500 KB Execution killed with signal 11
41 Halted 0 ms 0 KB -