#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
struct Qu{
int s, t, x, y, id;
};
vt<pii>edge, weight;
vt<Qu>qq;
int n, m, q;
vt<pii>adj[mxn + 1];
int ans[mxn + 1], tin[mxn + 1], tout[mxn + 1], dep[mxn + 1], up[mxn + 1][17], tt = 0;
ll dep2[mxn + 1], cnt2[mxn + 1], w[mxn + 1];
struct ST{
ll st[4 * mxn + 1], lz[4 * mxn + 1];
void push(int nd, int l, int mid, int r){
st[nd << 1] += (mid - l + 1) * lz[nd]; lz[nd << 1] += lz[nd];
st[nd << 1 | 1] += (r - mid) * lz[nd]; lz[nd << 1 | 1] += lz[nd];
lz[nd] = 0;
}
void upd(int nd, int l, int r, int ql, int qr, ll v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
st[nd] += 1LL * (r - l + 1) * v; lz[nd] += v;
return;
}
int mid = (l + r) >> 1;
push(nd, l, mid, r);
upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
st[nd] = st[nd << 1] + st[nd << 1 | 1];
}
ll get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(0);
if(ql <= l && qr >= r){
return(st[nd]);
}
int mid = (l + r) >> 1;
push(nd, l, mid, r);
return(get(nd << 1, l, mid, ql, qr) + get(nd << 1 | 1, mid + 1, r, ql, qr));
}
ll single(int x){
return(get(1, 1, n, x, x));
}
void update(int u, ll v){
upd(1, 1, n, tin[u], tout[u], v);
}
};
ST cnt, sm;
int lca(int a, int b){
if(dep[a] < dep[b])swap(a, b);
int k = dep[a] - dep[b];
forr(i, 0, 17){
if(k & (1 << i)){
a = up[a][i];
}
}
if(a == b)return(a);
for(int i = 16; i >= 0; i--){
if(up[a][i] != up[b][i]){
a = up[a][i]; b = up[b][i];
}
}
return(up[a][0]);
}
void solve(int l, int r, vt<Qu>cand){
if(l > r || cand.empty())return;
int mid = (l + r) >> 1;
for(int i = l; i <= mid; i++){
int id = weight[i].se, u;
if(dep[edge[id].fi] > dep[edge[id].se])u = edge[id].fi;
else u = edge[id].se;
sm.update(u, weight[i].fi);
cnt.update(u, 1);
}
vt<Qu>yes, no;
for(auto [s, t, x, y, id]: cand){
ll w = sm.single(tin[s]) + sm.single(tin[t]) - 2 * sm.single(tin[lca(s, t)]);
int countt = cnt.single(tin[s]) + cnt.single(tin[t]) - 2 * cnt.single(tin[lca(s, t)]);
if(w <= y){
y -= w;
ans[id] += countt;
yes.pb({s, t, x, y, id});
}else{
no.pb({s, t, x, y, id});
}
}
for(int i = l; i <= mid; i++){
int id = weight[i].se, u;
if(dep[edge[id].fi] > dep[edge[id].se])u = edge[id].fi;
else u = edge[id].se;
sm.update(u, -weight[i].fi);
cnt.update(u, -1);
}
solve(l, mid - 1, no); solve(mid + 1, r, yes);
}
void dfs(int s, int pre){
tin[s] = ++tt;
for(auto [i, id]: adj[s]){
if(i != pre){
dep2[i] = dep2[s] + cnt2[id];
up[i][0] = s; dep[i] = dep[s] + 1;
dfs(i, s);
}
}
tout[s] = tt;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
edge.resize(n + 1);
forr(i, 1, n){
int u, v; cin >> u >> v;
edge[i] = {u, v};
adj[u].pb({v, i}); adj[v].pb({u, i});
}
forr(i, 0, m){
int p, c; cin >> p >> c;
weight.pb({c, p});
cnt2[p]++;
}
sort(weight.begin(), weight.end());
dfs(1, -1);
for(int i = 1; i < 17; i++){
for(int j= 1; j <= n; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
forr(i, 0, q){
int s, t, x, y; cin >> s >> t >> x >> y;
qq.pb({s, t, x, y, i});
}
solve(0, weight.size() - 1, qq);
forr(i, 0, q){
//cout << ans[i] << " ";
auto [s, t, x, y, id] = qq[i];
int len = dep2[s] + dep2[t] - 2 * dep2[lca(s, t)];
//cout << len << " ";
if(len - ans[i] <= x){
cout << x - (len - ans[i]) << "\n";
}else{
cout << -1 << "\n";
}
}
return(0);
}
Compilation message
currencies.cpp: In function 'void solve(int, int, std::vector<Qu>)':
currencies.cpp:105:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | for(auto [s, t, x, y, id]: cand){
| ^
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
129 | for(auto [i, id]: adj[s]){
| ^
currencies.cpp: In function 'int main()':
currencies.cpp:168:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
168 | auto [s, t, x, y, id] = qq[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
6104 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
6568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
6644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
6104 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
