| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1257636 | shafi_root | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
/* _In The Name Of God_ */
#include <bits/stdc++.h>
using namespace std;
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
#define pb push_back
#define F first
#define S second
#define lc id << 1
#define rc lc|1
#define mid ((l + r)/2)
// #define int long long
typedef pair<int, int> pii;
typedef long long ll;
const ll MOD = 1e9 + 7; // 998244353;
const ll INF = 1e9 + 1;
const int MXN = 1e5 + 5;
const int LOG = 18;
ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }
int n, m, q, L[MXN], R[MXN], M[MXN], X[MXN], s[MXN], t[MXN],
num[MXN], h[MXN], st[MXN], fn[MXN], cnt[MXN], timer=1, sum, par[LOG][MXN], val[MXN], Ans[MXN];
ll fen[MXN], Y[MXN];
pii E[MXN];
vector<int> adj[MXN], Que[MXN];
vector<pii> vec;
void dfs(int v, int p) {
val[v] = sum;
h[v] = h[p] + (v!=p);
st[v] = timer++;
par[0][v] = p;
for (int i = 1; i < LOG; i++) {
par[i][v] = par[i-1][par[i-1][v]];
}
for (int x : adj[v]) {
int u = E[x].F ^ E[x].S ^ v;
if (u != p) {
sum += cnt[x];
dfs(u, v);
sum -= cnt[x];
}
}
fn[v] = timer;
}
int jump(int v, int k) {
for (int i = 0; i < LOG; i++) {
if (k >> i & 1) v = par[i][v];
}
return v;
}
int LCA(int u, int v) {
if (h[u] < h[v]) swap(u, v);
u = jump(u, h[u] - h[v]);
if (u == v) return u;
for (int i = LOG-1; i >= 0; i--) {
if (par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
}
return par[0][u];
}
void upd(int p, ll x) {
for (; p < n+3; p += p &- p) {
fen[p] += x;
}
// fen[p]+=x;
}
ll get(int p) {
ll res = 0;
for (; p; p -= p &- p) {
res += fen[p];
}
// for (int i = 1; i <= p; i++) res += fen[i];
return res;
}
void Solve() {
fill(fen, fen + n+3, 0ll);
for (int i = 0; i < m; i++) {
int p = h[E[vec[i].S].F] > h[E[vec[i].S].S] ? E[vec[i].S].F : E[vec[i].S].S;
upd(st[p], vec[i].F);
upd(fn[p], -vec[i].F);
for (int qr : Que[i]) {
ll ans = get(st[s[qr]]) + get(st[t[qr]]) - 2ll*get(st[LCA(s[qr], t[qr])]);
if (ans <= X[qr]) L[qr] = i;
else R[qr] = i;
}
}
}
void Sol() {
fill(fen, fen + n+3, 0ll);
for (int i = 0; i < m; i++) {
int p = h[E[vec[i].S].F] > h[E[vec[i].S].S] ? E[vec[i].S].F : E[vec[i].S].S;
upd(st[p], 1);
upd(fn[p], -1);
for (int qr : Que[i]) {
ll ans = get(st[s[qr]]) + get(st[t[qr]]) - 2ll*get(st[LCA(s[qr], t[qr])]);
Ans[qr] = num[qr] - ans;
}
}
}
void _solve() {
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
E[i].F = u, E[i].S = v;
adj[u].pb(i);
adj[v].pb(i);
}
for (int i = 1; i <= m; i++) {
int v, c;
cin >> v >> c;
vec.pb({c, v});
cnt[v]++;
}
dfs(1, 1);
sort(vec.begin(), vec.end());
for (int i = 1; i <= q; i++) {
cin >> s[i] >> t[i] >> Y[i] >> X[i];
num[i] = val[s[i]] + val[t[i]] - 2*val[LCA(s[i], t[i])];
L[i] = -1, R[i] = m; // L[i]+1 silver, if we can L[i] = mid
}
for (int step = 0; step < LOG; step++) {
for (int i = 0; i <= m; i++) Que[i].clear();
for (int i = 1; i <= q; i++) Que[(L[i]+R[i])/2].pb(i);
Solve();
}
for (int i = 0; i <= m; i++) Que[i].clear();
for (int i = 1; i <= q; i++) {
if (L[i] != -1) Que[L[i]].pb(i);
else {
Ans[i] = num[i];
}
}
Sol();
for (int i = 1; i <= q; i++) {
cout << max(-1, Y[i] - Ans[i]) << '\n';
}
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int _ = 1;
// cin >> _;
while (_--) _solve();
return 0.0;
}