| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243800 | Double_Slash | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;
int n, m, q, dep[100001], S[100001], E[100001], st[200000][18], def[100000], s[100000], t[100000], x[100000], lca[100000], ans[100000], cnt[100000];
ll y[100000], sum[100000];
vector<int> adj[100001];
vector<pint> c;
template <class T>
struct St {
int n;
vector<T> st;
St(int n) : n(n), st(n << 1) {}
void upd(int l, int r, const T &v) {
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) st[l++] += v;
if (r & 1) st[--r] += v;
}
}
T operator()(int i) {
T ret = 0;
for (i += n; i; i >>= 1) ret += st[i];
return ret;
}
};
void dfs(int i, int p = 0) {
st[S[i]][0] = i;
for (int j: adj[i]) {
if (j == p) continue;
dep[j] = dep[i] + 1;
S[j] = E[j] = E[i] + 1;
dfs(j, i);
st[E[i] = E[j] + 1][0] = i;
}
}
void dfs2(int i, int p = 0) {
for (int j: adj[i]) {
if (j == p) continue;
def[j] += def[i];
dfs2(j, i);
}
}
template <bool silver, class T>
void calc(int ans[], T cur[]) {
vector<pint> v = c;
for (int i = q; i--;) v.emplace_back(ans[i], i);
sort(all(v));
St<T> st{E[1] + 1};
for (auto &[a, i]: v) {
if (i < 0) {
if constexpr (silver) st.upd(S[-i], E[-i] + 1, a);
else st.upd(S[-i], E[-i] + 1, 1);
} else cur[i] = st(S[s[i]]) + st(S[t[i]]) - st(S[lca[i]]) * 2;
}
}
int main() {
cin >> n >> m >> q;
pint edges[n - 1];
for (auto &[a, b]: edges) {
cin >> a >> b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
dfs(1);
auto mn = [&] (int i, int j) { return dep[i] < dep[j] ? i : j; };
c.resize(m);
for (auto &[ci, i]: c) {
cin >> i;
if (dep[edges[i - 1].first] > dep[edges[i - 1].second]) swap(edges[i - 1].first, edges[i - 1].second);
++def[i = edges[i - 1].second];
cin >> ci;
i *= -1;
}
dfs2(1);
for (int j = 1; j < 18; ++j) {
for (int i = 0; i + (1 << j) - 1 <= E[1]; ++i) st[i][j] = mn(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
for (int i = q; i--;) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
int l = min(S[s[i]], S[t[i]]);
int r = max(E[s[i]], E[t[i]]);
int j = __lg(r - l + 1);
lca[i] = mn(st[l][j], st[r - (1 << j) + 1][j]);
}
for (int k = 30; k--;) {
for (int i = q; i--;) ans[i] += 1 << k;
calc<true>(ans, sum);
for (int i = q; i--;) {
if (sum[i] > y[i]) ans[i] -= 1 << k;
}
}
calc<false>(ans, cnt);
calc<true>(ans, sum);
for (int i = q; i--;) {
y[i] -= sum[i];
cnt[i] = max(0, def[s[i]] + def[t[i]] - def[lca[i]] * 2 - cnt[i] - y[i] / (ans[i] + 1));
if (cnt[i] > x[i]) cout << "-1\n";
else cout << x[i] - cnt[i] << endl;
}
}