| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 872855 | MinaRagy06 | Two Currencies (JOI23_currencies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l + r) >> 1)
const int N = 100'005;
cont ll inf = 1e18;
int anc[N][17], st[N], en[N], t;
ll h[N];
vector<array<int, 2>> adj[N];
array<ll, 2> a[N];
void dfs(int i, int par, ll d) {
h[i] = d;
anc[i][0] = par;
for (int j = 1; j < 17; j++) {
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
st[i] = t++;
for (auto [nxt, w] : adj[i]) {
if (nxt == par) continue;
dfs(nxt, i, d + w);
}
en[i] = t;
}
int getlca(int u, int v) {
if (st[u] > st[v]) swap(u, v);
if (st[u] <= st[v] && en[v] <= en[u]) {
return u;
}
for (int j = 16; j >= 0; j--) {
if (!(st[anc[u][j]] <= st[v] && en[v] <= en[anc[u][j]])) {
u = anc[u][j];
}
}
return anc[u][0];
}
struct node {
ll val = 0;
int cnt = 0;
node(int x) {
val = x, cnt = 1;
}
node() {}
node& operator+=(node y) {
val += y.val;
cnt += y.cnt;
return *this;
}
friend node operator+(node x, node y) {
return x += y;
}
node& operator-=(node y) {
val -= y.val;
cnt -= y.cnt;
return *this;
}
friend node operator-(node x, node y) {
return x -= y;
}
node& operator*=(int x) {
val *= x;
cnt *= x;
return *this;
}
friend node operator*(int x, node y) {
return y *= x;
}
};
node lazy[1 << 18];
void upd(int i, int l, int r, int s, int e, node v) {
if (s <= l && r <= e) {
lazy[i] += v;
return;
}
if (r < s || e < l) {
return;
}
upd(i << 1, l, mid, s, e, v);
upd(i << 1 | 1, mid + 1, r, s, e, v);
}
node get(int i, int l, int r, int x) {
if (l == r) {
return lazy[i];
}
if (x <= mid) {
return get(i << 1, l, mid, x) + lazy[i];
} else {
return get(i << 1 | 1, mid + 1, r, x) + lazy[i];
}
}
int n, m, q;
node height(int u) {
return get(1, 0, n - 1, st[u]);
}
vector<array<ll, 7>> ask[2][N];
vector<array<ll, 5>> ansask[N];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q;
array<int, 3> edges[n - 1];
for (int i = 0; i < n - 1; i++) {
auto &[u, v, cnt] = edges[i];
cin >> u >> v;
cnt = 0;
}
for (int i = 0; i < m; i++) {
cin >> a[i][1] >> a[i][0];
a[i][1]--;
edges[a[i][1]][2]++;
}
for (auto &[u, v, cnt] : edges) {
adj[u].push_back({v, cnt});
adj[v].push_back({u, cnt});
}
dfs(1, 1, 0);
for (auto &[u, v, cnt] : edges) {
if (st[u] > st[v]) {
swap(u, v);
}
}
sort(a, a + m);
array<ll, 4> query[q];
for (int i = 0; i < q; i++) {
auto &[u, v, x, y] = query[i];
cin >> u >> v >> y >> x;
ask[0][m >> 1].push_back({u, v, x, y, 0, m, i});
}
int cur = 0;
for (int _ = 0; _ < 17; _++) {
bool done = 0;
for (int i = 0; i < (1 << 18); i++) {
lazy[i] = node();
}
for (int md = 0; md <= m; md++) {
ask[cur ^ 1][md].clear();
}
int idx = -1;
for (int md = 0; md <= m; md++) {
if (md && idx + 1 < m) {
ll tar = a[idx + 1][0];
while (idx + 1 < m && a[idx + 1][0] == tar) {
idx++;
int e = a[idx][1];
int v = edges[e][1];
upd(1, 0, n - 1, st[v], en[v], a[idx][0]);
}
}
for (auto &[u, v, x, y, l, r, qidx] : ask[cur][md]) {
done = 1;
int lca = getlca(u, v);
node ttl = height(u) + height(v) - 2 * height(lca);
if (ttl.val <= x) {
l = md + 1;
} else {
r = md - 1;
}
if (l <= r) {
ask[cur ^ 1][(l + r) >> 1].push_back({u, v, x, y, l, r, qidx});
} else {
ansask[r].push_back({u, v, x, y, qidx});
}
}
}
if (!done) break;
cur ^= 1;
}
ll ans[q];
memset(ans, '?', sizeof ans);
int idx = -1;
for (int i = 0; i < (1 << 18); i++) {
lazy[i] = node();
}
for (int i = 0; i <= m; i++) {
if (i && idx + 1 < m) {
ll tar = a[idx + 1][0];
while (idx + 1 < m && a[idx + 1][0] == tar) {
idx++;
int e = a[idx][1];
int v = edges[e][1];
upd(1, 0, n - 1, st[v], en[v], a[idx][0]);
}
}
for (auto &[u, v, x, y, qidx] : ansask[i]) {
int lca = getlca(u, v);
node ttl = height(u) + height(v) - 2 * height(lca);
ll dist = h[u] + h[v] - 2 * h[lca];
x -= ttl.val;
dist -= ttl.cnt;
ll nxt = inf;
if (idx + 1 < m) {
nxt = a[idx + 1][0];
}
ll rem = min((ll)dist, x / nxt);
dist -= rem;
y -= dist;
ans[qidx] = y;
}
}
for (int i = 0; i < q; i++) {
if (ans[i] < 0) {
cout << "-1\n";
} else {
cout << ans[i] << '\n';
}
}
return 0;
}