#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 10;
#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define fi first
#define se second
// parallel binser + hld
struct segtree{
pli st[MX << 1];
void build(){
for(int i = 0; i < (MX << 1); i++) st[i] = {0ll, 0};
}
void upd(int p, int v){
for(p += MX, st[p].fi += v, st[p].se += 1, p >>= 1; p > 0; p >>= 1){
st[p].fi = st[p << 1].fi + st[p << 1|1].fi;
st[p].se = st[p << 1].se + st[p << 1|1].se;
}
}
pli que(int l, int r){
pli res = {0, 0};
for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
if(l & 1){
res.fi += st[l].fi, res.se += st[l].se;
l++;
}
if(r & 1){
--r;
res.fi += st[r].fi, res.se += st[r].se;
}
}
return res;
}
} S;
struct hld{
int sz[MX], dep[MX], par[MX], in[MX], out[MX], head[MX], tim = 0;
vector<int> adj[MX];
void ae(int u, int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int u, int v){
if(v != 0) adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
par[u] = v;
dep[u] = dep[v] + 1;
sz[u] = 1;
for(int& nx : adj[u]){
dfs(nx, u);
sz[u] += sz[nx];
if(sz[nx] > sz[adj[u][0]]) swap(nx, adj[u][0]);
}
}
void dfs2(int u, int v){
in[u] = ++tim;
for(int nx : adj[u]){
if(nx == adj[u][0]) head[nx] = head[u];
else head[nx] = nx;
dfs2(nx, u);
}
out[u] = tim;
}
void init(){
dfs(1, 0);
head[1] = 1;
dfs2(1, 0);
}
void upd(int nd, int v){
S.upd(in[nd], v);
}
pli que(int u, int v){
pli res = {0, 0};
for(; head[u] != head[v]; v = par[head[v]]){
if(dep[head[u]] > dep[head[v]]) swap(u, v);
pli nw = S.que(in[head[v]], in[v]);
res.fi += nw.fi, res.se += nw.se;
}
if(dep[u] > dep[v]) swap(u, v);
pli nw = S.que(in[u] + 1, in[v]);
res.fi += nw.fi, res.se += nw.se;
return res;
}
} H;
struct query{
int s, t, x; ll y; int l, r, mid, id;
query(int s = 0, int t = 0, int x = 0, ll y = 0, int l = 0, int r = 0, int id = 0) :
s(s), t(t), x(x), y(y), l(l), r(r), mid(l + r >> 1), id(id) {}
bool operator < (const query other) const {
return mid < other.mid;
}
};
vector<query> queries[2];
int N, M, Q; pli ans[MX];
vector<pii> edges, ch;
int qs[MX], qt[MX], X[MX]; ll Y[MX];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> Q;
for(int i = 1; i < N; i++){
int u, v; cin >> u >> v;
edges.push_back({u, v});
H.ae(u, v);
}
for(int i = 0; i < M; i++){
int p, c; cin >> p >> c; p--;
ch.push_back({c, p});
}
sort(ch.begin(), ch.end());
// cout << "init\n";
H.init();
for(int i = 0; i < N - 1; i++){
if(H.dep[edges[i].fi] > H.dep[edges[i].se]) swap(edges[i].fi, edges[i].se);
}
for(int i = 0; i < Q; i++){
int s, t, x; ll y; cin >> s >> t >> x >> y; qs[i] = s, qt[i] = t, X[i] = x, Y[i] = y;
query curr = query(s, t, x, y, 0, M, i);
// 0 is none, 1 is index 0, 2 is index 0 to 1, ..., M is index 0 to M-1
queries[0].push_back(curr);
}
int id = 0;
sort(queries[0].begin(), queries[0].end());
S.build();
for(; !queries[id].empty(); ){
int j = 0;
// cout << "query " << id << '\n';
for(query& curr : queries[id]){
for(; j < M && j < curr.mid; j++) H.upd(edges[ch[j].se].se, ch[j].fi);
pli nw = H.que(curr.s, curr.t);
// cout << "at j " << curr.mid << " from " << curr.s << " to " << curr.t << " " << nw.fi << '\n';
if(nw.fi <= curr.y){
ans[curr.id] = nw;
query nx = query(curr.s, curr.t, curr.x, curr.y, curr.mid + 1, curr.r, curr.id);
if(nx.l <= nx.r) queries[id ^ 1].push_back(nx);
}else{
query nx = query(curr.s, curr.t, curr.x, curr.y, curr.l, curr.mid - 1, curr.id);
if(nx.l <= nx.r) queries[id ^ 1].push_back(nx);
}
}
queries[id].clear();
id ^= 1;
sort(queries[id].begin(), queries[id].end());
S.build();
}
for(int i = 0; i < M; i++) H.upd(edges[ch[i].se].se, 1);
for(int i = 0; i < Q; i++){
// cout << "found " << ans[i].fi << " " << ans[i].se << '\n';
int used_gold = H.que(qs[i], qt[i]).se - ans[i].se;
assert(ans[i].fi <= Y[i]);
if(used_gold > X[i]) cout << -1 << '\n';
else cout << X[i] - used_gold << '\n';
}
}
Compilation message
currencies.cpp: In constructor 'query::query(int, int, int, long long int, int, int, int)':
currencies.cpp:105:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | s(s), t(t), x(x), y(y), l(l), r(r), mid(l + r >> 1), id(id) {}
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
8 ms |
6236 KB |
Output is correct |
6 |
Correct |
9 ms |
6392 KB |
Output is correct |
7 |
Correct |
9 ms |
6228 KB |
Output is correct |
8 |
Correct |
10 ms |
6356 KB |
Output is correct |
9 |
Correct |
10 ms |
6356 KB |
Output is correct |
10 |
Correct |
10 ms |
6292 KB |
Output is correct |
11 |
Correct |
10 ms |
6356 KB |
Output is correct |
12 |
Correct |
10 ms |
6356 KB |
Output is correct |
13 |
Correct |
10 ms |
6404 KB |
Output is correct |
14 |
Correct |
10 ms |
6428 KB |
Output is correct |
15 |
Correct |
11 ms |
6356 KB |
Output is correct |
16 |
Correct |
12 ms |
6424 KB |
Output is correct |
17 |
Correct |
10 ms |
6340 KB |
Output is correct |
18 |
Correct |
10 ms |
6428 KB |
Output is correct |
19 |
Correct |
7 ms |
6404 KB |
Output is correct |
20 |
Correct |
7 ms |
6356 KB |
Output is correct |
21 |
Correct |
8 ms |
6356 KB |
Output is correct |
22 |
Correct |
7 ms |
6284 KB |
Output is correct |
23 |
Correct |
9 ms |
6316 KB |
Output is correct |
24 |
Correct |
9 ms |
6356 KB |
Output is correct |
25 |
Correct |
9 ms |
6416 KB |
Output is correct |
26 |
Correct |
8 ms |
6308 KB |
Output is correct |
27 |
Correct |
10 ms |
6404 KB |
Output is correct |
28 |
Correct |
8 ms |
6356 KB |
Output is correct |
29 |
Correct |
7 ms |
6356 KB |
Output is correct |
30 |
Correct |
10 ms |
6356 KB |
Output is correct |
31 |
Correct |
10 ms |
6296 KB |
Output is correct |
32 |
Correct |
10 ms |
6296 KB |
Output is correct |
33 |
Correct |
9 ms |
6460 KB |
Output is correct |
34 |
Correct |
9 ms |
6484 KB |
Output is correct |
35 |
Correct |
9 ms |
6484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
10 ms |
6356 KB |
Output is correct |
3 |
Correct |
10 ms |
6404 KB |
Output is correct |
4 |
Correct |
10 ms |
6356 KB |
Output is correct |
5 |
Correct |
482 ms |
25224 KB |
Output is correct |
6 |
Correct |
632 ms |
30124 KB |
Output is correct |
7 |
Correct |
592 ms |
30360 KB |
Output is correct |
8 |
Correct |
467 ms |
29064 KB |
Output is correct |
9 |
Correct |
516 ms |
23724 KB |
Output is correct |
10 |
Correct |
724 ms |
32692 KB |
Output is correct |
11 |
Correct |
741 ms |
32772 KB |
Output is correct |
12 |
Correct |
757 ms |
32796 KB |
Output is correct |
13 |
Correct |
725 ms |
32676 KB |
Output is correct |
14 |
Correct |
690 ms |
32668 KB |
Output is correct |
15 |
Correct |
527 ms |
38920 KB |
Output is correct |
16 |
Correct |
507 ms |
39308 KB |
Output is correct |
17 |
Correct |
526 ms |
38708 KB |
Output is correct |
18 |
Correct |
862 ms |
32968 KB |
Output is correct |
19 |
Correct |
873 ms |
33020 KB |
Output is correct |
20 |
Correct |
905 ms |
33060 KB |
Output is correct |
21 |
Correct |
291 ms |
32364 KB |
Output is correct |
22 |
Correct |
272 ms |
32552 KB |
Output is correct |
23 |
Correct |
280 ms |
32576 KB |
Output is correct |
24 |
Correct |
282 ms |
32568 KB |
Output is correct |
25 |
Correct |
528 ms |
32948 KB |
Output is correct |
26 |
Correct |
538 ms |
32984 KB |
Output is correct |
27 |
Correct |
529 ms |
32940 KB |
Output is correct |
28 |
Correct |
291 ms |
32572 KB |
Output is correct |
29 |
Correct |
308 ms |
32560 KB |
Output is correct |
30 |
Correct |
363 ms |
32688 KB |
Output is correct |
31 |
Correct |
352 ms |
32740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
9 ms |
6484 KB |
Output is correct |
3 |
Correct |
9 ms |
6456 KB |
Output is correct |
4 |
Correct |
9 ms |
6484 KB |
Output is correct |
5 |
Correct |
339 ms |
32996 KB |
Output is correct |
6 |
Correct |
330 ms |
35556 KB |
Output is correct |
7 |
Correct |
455 ms |
32180 KB |
Output is correct |
8 |
Correct |
515 ms |
39344 KB |
Output is correct |
9 |
Correct |
521 ms |
39348 KB |
Output is correct |
10 |
Correct |
518 ms |
39396 KB |
Output is correct |
11 |
Correct |
466 ms |
39368 KB |
Output is correct |
12 |
Correct |
461 ms |
39484 KB |
Output is correct |
13 |
Correct |
474 ms |
39476 KB |
Output is correct |
14 |
Correct |
322 ms |
39336 KB |
Output is correct |
15 |
Correct |
311 ms |
39304 KB |
Output is correct |
16 |
Correct |
354 ms |
39400 KB |
Output is correct |
17 |
Correct |
392 ms |
39444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
8 ms |
6236 KB |
Output is correct |
6 |
Correct |
9 ms |
6392 KB |
Output is correct |
7 |
Correct |
9 ms |
6228 KB |
Output is correct |
8 |
Correct |
10 ms |
6356 KB |
Output is correct |
9 |
Correct |
10 ms |
6356 KB |
Output is correct |
10 |
Correct |
10 ms |
6292 KB |
Output is correct |
11 |
Correct |
10 ms |
6356 KB |
Output is correct |
12 |
Correct |
10 ms |
6356 KB |
Output is correct |
13 |
Correct |
10 ms |
6404 KB |
Output is correct |
14 |
Correct |
10 ms |
6428 KB |
Output is correct |
15 |
Correct |
11 ms |
6356 KB |
Output is correct |
16 |
Correct |
12 ms |
6424 KB |
Output is correct |
17 |
Correct |
10 ms |
6340 KB |
Output is correct |
18 |
Correct |
10 ms |
6428 KB |
Output is correct |
19 |
Correct |
7 ms |
6404 KB |
Output is correct |
20 |
Correct |
7 ms |
6356 KB |
Output is correct |
21 |
Correct |
8 ms |
6356 KB |
Output is correct |
22 |
Correct |
7 ms |
6284 KB |
Output is correct |
23 |
Correct |
9 ms |
6316 KB |
Output is correct |
24 |
Correct |
9 ms |
6356 KB |
Output is correct |
25 |
Correct |
9 ms |
6416 KB |
Output is correct |
26 |
Correct |
8 ms |
6308 KB |
Output is correct |
27 |
Correct |
10 ms |
6404 KB |
Output is correct |
28 |
Correct |
8 ms |
6356 KB |
Output is correct |
29 |
Correct |
7 ms |
6356 KB |
Output is correct |
30 |
Correct |
10 ms |
6356 KB |
Output is correct |
31 |
Correct |
10 ms |
6296 KB |
Output is correct |
32 |
Correct |
10 ms |
6296 KB |
Output is correct |
33 |
Correct |
9 ms |
6460 KB |
Output is correct |
34 |
Correct |
9 ms |
6484 KB |
Output is correct |
35 |
Correct |
9 ms |
6484 KB |
Output is correct |
36 |
Correct |
3 ms |
5844 KB |
Output is correct |
37 |
Correct |
10 ms |
6356 KB |
Output is correct |
38 |
Correct |
10 ms |
6404 KB |
Output is correct |
39 |
Correct |
10 ms |
6356 KB |
Output is correct |
40 |
Correct |
482 ms |
25224 KB |
Output is correct |
41 |
Correct |
632 ms |
30124 KB |
Output is correct |
42 |
Correct |
592 ms |
30360 KB |
Output is correct |
43 |
Correct |
467 ms |
29064 KB |
Output is correct |
44 |
Correct |
516 ms |
23724 KB |
Output is correct |
45 |
Correct |
724 ms |
32692 KB |
Output is correct |
46 |
Correct |
741 ms |
32772 KB |
Output is correct |
47 |
Correct |
757 ms |
32796 KB |
Output is correct |
48 |
Correct |
725 ms |
32676 KB |
Output is correct |
49 |
Correct |
690 ms |
32668 KB |
Output is correct |
50 |
Correct |
527 ms |
38920 KB |
Output is correct |
51 |
Correct |
507 ms |
39308 KB |
Output is correct |
52 |
Correct |
526 ms |
38708 KB |
Output is correct |
53 |
Correct |
862 ms |
32968 KB |
Output is correct |
54 |
Correct |
873 ms |
33020 KB |
Output is correct |
55 |
Correct |
905 ms |
33060 KB |
Output is correct |
56 |
Correct |
291 ms |
32364 KB |
Output is correct |
57 |
Correct |
272 ms |
32552 KB |
Output is correct |
58 |
Correct |
280 ms |
32576 KB |
Output is correct |
59 |
Correct |
282 ms |
32568 KB |
Output is correct |
60 |
Correct |
528 ms |
32948 KB |
Output is correct |
61 |
Correct |
538 ms |
32984 KB |
Output is correct |
62 |
Correct |
529 ms |
32940 KB |
Output is correct |
63 |
Correct |
291 ms |
32572 KB |
Output is correct |
64 |
Correct |
308 ms |
32560 KB |
Output is correct |
65 |
Correct |
363 ms |
32688 KB |
Output is correct |
66 |
Correct |
352 ms |
32740 KB |
Output is correct |
67 |
Correct |
3 ms |
5844 KB |
Output is correct |
68 |
Correct |
9 ms |
6484 KB |
Output is correct |
69 |
Correct |
9 ms |
6456 KB |
Output is correct |
70 |
Correct |
9 ms |
6484 KB |
Output is correct |
71 |
Correct |
339 ms |
32996 KB |
Output is correct |
72 |
Correct |
330 ms |
35556 KB |
Output is correct |
73 |
Correct |
455 ms |
32180 KB |
Output is correct |
74 |
Correct |
515 ms |
39344 KB |
Output is correct |
75 |
Correct |
521 ms |
39348 KB |
Output is correct |
76 |
Correct |
518 ms |
39396 KB |
Output is correct |
77 |
Correct |
466 ms |
39368 KB |
Output is correct |
78 |
Correct |
461 ms |
39484 KB |
Output is correct |
79 |
Correct |
474 ms |
39476 KB |
Output is correct |
80 |
Correct |
322 ms |
39336 KB |
Output is correct |
81 |
Correct |
311 ms |
39304 KB |
Output is correct |
82 |
Correct |
354 ms |
39400 KB |
Output is correct |
83 |
Correct |
392 ms |
39444 KB |
Output is correct |
84 |
Correct |
504 ms |
24244 KB |
Output is correct |
85 |
Correct |
557 ms |
27456 KB |
Output is correct |
86 |
Correct |
496 ms |
26868 KB |
Output is correct |
87 |
Correct |
729 ms |
32624 KB |
Output is correct |
88 |
Correct |
743 ms |
32616 KB |
Output is correct |
89 |
Correct |
790 ms |
32644 KB |
Output is correct |
90 |
Correct |
746 ms |
32608 KB |
Output is correct |
91 |
Correct |
776 ms |
32732 KB |
Output is correct |
92 |
Correct |
610 ms |
37060 KB |
Output is correct |
93 |
Correct |
581 ms |
38340 KB |
Output is correct |
94 |
Correct |
948 ms |
33040 KB |
Output is correct |
95 |
Correct |
948 ms |
32972 KB |
Output is correct |
96 |
Correct |
922 ms |
32968 KB |
Output is correct |
97 |
Correct |
937 ms |
32988 KB |
Output is correct |
98 |
Correct |
350 ms |
32516 KB |
Output is correct |
99 |
Correct |
345 ms |
32432 KB |
Output is correct |
100 |
Correct |
350 ms |
32556 KB |
Output is correct |
101 |
Correct |
342 ms |
32508 KB |
Output is correct |
102 |
Correct |
585 ms |
32976 KB |
Output is correct |
103 |
Correct |
556 ms |
32916 KB |
Output is correct |
104 |
Correct |
587 ms |
33048 KB |
Output is correct |
105 |
Correct |
367 ms |
32696 KB |
Output is correct |
106 |
Correct |
368 ms |
32608 KB |
Output is correct |
107 |
Correct |
404 ms |
32560 KB |
Output is correct |
108 |
Correct |
394 ms |
32556 KB |
Output is correct |