#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NM = 1e5, LOG = 16;
struct checkpt{
int v, c;
};
struct query{
int id, s, t, lca, x, y, l, r, mid, res;
};
int N, M, Q, u[NM+5], v[NM+5], t = 0;
vector <int> adj[NM+5];
int parent[NM+5], h[NM+5], st[NM+5], en[NM+5];
int jump[NM+5][LOG+5];
checkpt a[NM+5];
query b[NM+5];
int bit[2*NM+5], bit2[2*NM+5];
int ans[NM+5];
void DFS(int u){
st[u] = ++t;
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
if (h[v] != -1) continue;
parent[v] = u;
h[v] = h[u]+1;
DFS(v);
}
en[u] = ++t;
}
void build(){
for (int i = 1; i <= N; i++) jump[i][0] = parent[i];
for (int j = 1; j <= LOG; j++)
for (int i = 1; i <= N; i++)
if (jump[i][j-1] != -1) jump[i][j] = jump[jump[i][j-1]][j-1];
else jump[i][j] = -1;
}
int LCA(int u, int v){
if (h[u] < h[v]) swap(u, v);
for (int i = LOG; i >= 0; i--)
if (h[u]-(1<<i) >= h[v]) u = jump[u][i];
if (u == v) return u;
for (int i = LOG; i >= 0; i--)
if (jump[u][i] != -1 && jump[u][i] != jump[v][i]){
u = jump[u][i];
v = jump[v][i];
}
return parent[u];
}
bool cmp(checkpt a, checkpt b){
return a.c < b.c;
}
bool cmp2(query a, query b){
if (a.l > a.r) return 0;
if (b.l > b.r) return 1;
return a.mid < b.mid;
}
void update(int bit[NM+5], int p, int v){
while (p <= 2*N){
bit[p] += v;
p += p & (-p);
}
}
int get(int bit[NM+5], int p){
int res = 0;
while (p > 0){
res += bit[p];
p -= p & (-p);
}
return res;
}
int get_range(int bit[NM+5], int l, int r){
return get(bit, r)-get(bit, l-1);
}
int get_path(int bit[NM+5], int s, int t, int lca){
return get_range(bit, st[lca], st[s])+get_range(bit, st[lca], st[t])-2*get_range(bit, st[lca], st[lca]);
}
void pbs(){
sort(b+1, b+1+Q, cmp2);
memset(bit, 0, sizeof(bit));
memset(bit2, 0, sizeof(bit2));
for (int i = 1; i <= M; i++){
update(bit, st[a[i].v], 1);
update(bit, en[a[i].v], -1);
}
int j = 1;
for (int i = 1; i <= Q; i++){
if (b[i].l > b[i].r) break;
while (j <= b[i].mid){
update(bit, st[a[j].v], -1);
update(bit, en[a[j].v], 1);
update(bit2, st[a[j].v], a[j].c);
update(bit2, en[a[j].v], -a[j].c);
j++;
}
int tmp = get_path(bit2, b[i].s, b[i].t, b[i].lca);
if (tmp <= b[i].y){
b[i].res = get_path(bit, b[i].s, b[i].t, b[i].lca);
b[i].l = b[i].mid+1;
}
else b[i].r = b[i].mid-1;
b[i].mid = (b[i].l+b[i].r)/2;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> Q;
for (int i = 1; i < N; i++){
cin >> u[i] >> v[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
parent[1] = -1, h[1] = 0;
for (int i = 2; i <= N; i++) h[i] = -1;
DFS(1);
build();
for (int i = 1; i <= M; i++){
int p; cin >> p;
if (parent[v[p]] == u[p]) a[i].v = v[p]; else a[i].v = u[p];
cin >> a[i].c;
}
sort(a+1, a+1+M, cmp);
for (int i = 1; i <= Q; i++){
b[i].id = i;
cin >> b[i].s >> b[i].t >> b[i].x >> b[i].y;
if (st[b[i].s] > st[b[i].t]) swap(b[i].s, b[i].t);
b[i].lca = LCA(b[i].s, b[i].t);
b[i].l = 0, b[i].r = M, b[i].mid = M/2;
}
for (int i = 0; (1<<i) <= M+1; i++)
pbs();
for (int i = 1; i <= Q; i++){
if (b[i].res > b[i].x) ans[b[i].id] = -1;
else ans[b[i].id] = b[i].x-b[i].res;
}
for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
return 0;
}
Compilation message
currencies.cpp: In function 'void DFS(long long int)':
currencies.cpp:27:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int i = 0; i < adj[u].size(); i++){
| ~~^~~~~~~~~~~~~~~
# |
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 |
2 ms |
5844 KB |
Output is correct |
4 |
Correct |
2 ms |
5844 KB |
Output is correct |
5 |
Correct |
8 ms |
6440 KB |
Output is correct |
6 |
Correct |
9 ms |
6484 KB |
Output is correct |
7 |
Correct |
9 ms |
6344 KB |
Output is correct |
8 |
Correct |
9 ms |
6484 KB |
Output is correct |
9 |
Correct |
13 ms |
6484 KB |
Output is correct |
10 |
Correct |
11 ms |
6564 KB |
Output is correct |
11 |
Correct |
10 ms |
6576 KB |
Output is correct |
12 |
Correct |
9 ms |
6548 KB |
Output is correct |
13 |
Correct |
10 ms |
6612 KB |
Output is correct |
14 |
Correct |
10 ms |
6600 KB |
Output is correct |
15 |
Correct |
10 ms |
6564 KB |
Output is correct |
16 |
Correct |
10 ms |
6484 KB |
Output is correct |
17 |
Correct |
10 ms |
6552 KB |
Output is correct |
18 |
Correct |
10 ms |
6564 KB |
Output is correct |
19 |
Correct |
8 ms |
6484 KB |
Output is correct |
20 |
Correct |
8 ms |
6484 KB |
Output is correct |
21 |
Correct |
9 ms |
6484 KB |
Output is correct |
22 |
Correct |
11 ms |
6484 KB |
Output is correct |
23 |
Correct |
9 ms |
6556 KB |
Output is correct |
24 |
Correct |
10 ms |
6552 KB |
Output is correct |
25 |
Correct |
9 ms |
6540 KB |
Output is correct |
26 |
Correct |
9 ms |
6484 KB |
Output is correct |
27 |
Correct |
9 ms |
6556 KB |
Output is correct |
28 |
Correct |
11 ms |
6488 KB |
Output is correct |
29 |
Correct |
9 ms |
6560 KB |
Output is correct |
30 |
Correct |
9 ms |
6484 KB |
Output is correct |
31 |
Correct |
10 ms |
6468 KB |
Output is correct |
32 |
Correct |
9 ms |
6484 KB |
Output is correct |
33 |
Correct |
10 ms |
6612 KB |
Output is correct |
34 |
Correct |
12 ms |
6624 KB |
Output is correct |
35 |
Correct |
10 ms |
6632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5820 KB |
Output is correct |
2 |
Correct |
10 ms |
6548 KB |
Output is correct |
3 |
Correct |
9 ms |
6484 KB |
Output is correct |
4 |
Correct |
9 ms |
6552 KB |
Output is correct |
5 |
Correct |
514 ms |
37596 KB |
Output is correct |
6 |
Correct |
676 ms |
32464 KB |
Output is correct |
7 |
Correct |
638 ms |
35544 KB |
Output is correct |
8 |
Correct |
449 ms |
34388 KB |
Output is correct |
9 |
Correct |
467 ms |
33824 KB |
Output is correct |
10 |
Correct |
725 ms |
41076 KB |
Output is correct |
11 |
Correct |
721 ms |
41136 KB |
Output is correct |
12 |
Correct |
729 ms |
41176 KB |
Output is correct |
13 |
Correct |
751 ms |
41124 KB |
Output is correct |
14 |
Correct |
718 ms |
41084 KB |
Output is correct |
15 |
Correct |
780 ms |
44888 KB |
Output is correct |
16 |
Correct |
879 ms |
45288 KB |
Output is correct |
17 |
Correct |
853 ms |
44684 KB |
Output is correct |
18 |
Correct |
777 ms |
40728 KB |
Output is correct |
19 |
Correct |
763 ms |
40580 KB |
Output is correct |
20 |
Correct |
779 ms |
40716 KB |
Output is correct |
21 |
Correct |
634 ms |
41148 KB |
Output is correct |
22 |
Correct |
609 ms |
41144 KB |
Output is correct |
23 |
Correct |
603 ms |
41136 KB |
Output is correct |
24 |
Correct |
658 ms |
41148 KB |
Output is correct |
25 |
Correct |
647 ms |
41324 KB |
Output is correct |
26 |
Correct |
640 ms |
41212 KB |
Output is correct |
27 |
Correct |
633 ms |
41208 KB |
Output is correct |
28 |
Correct |
612 ms |
41076 KB |
Output is correct |
29 |
Correct |
652 ms |
41036 KB |
Output is correct |
30 |
Correct |
611 ms |
41084 KB |
Output is correct |
31 |
Correct |
596 ms |
41088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
10 ms |
6612 KB |
Output is correct |
3 |
Correct |
10 ms |
6612 KB |
Output is correct |
4 |
Correct |
12 ms |
6552 KB |
Output is correct |
5 |
Correct |
483 ms |
40480 KB |
Output is correct |
6 |
Correct |
506 ms |
43852 KB |
Output is correct |
7 |
Correct |
654 ms |
36140 KB |
Output is correct |
8 |
Correct |
810 ms |
51028 KB |
Output is correct |
9 |
Correct |
792 ms |
51028 KB |
Output is correct |
10 |
Correct |
775 ms |
51024 KB |
Output is correct |
11 |
Correct |
677 ms |
51052 KB |
Output is correct |
12 |
Correct |
664 ms |
51184 KB |
Output is correct |
13 |
Correct |
660 ms |
51184 KB |
Output is correct |
14 |
Correct |
615 ms |
51064 KB |
Output is correct |
15 |
Correct |
611 ms |
50900 KB |
Output is correct |
16 |
Correct |
710 ms |
51180 KB |
Output is correct |
17 |
Correct |
684 ms |
51044 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 |
2 ms |
5844 KB |
Output is correct |
4 |
Correct |
2 ms |
5844 KB |
Output is correct |
5 |
Correct |
8 ms |
6440 KB |
Output is correct |
6 |
Correct |
9 ms |
6484 KB |
Output is correct |
7 |
Correct |
9 ms |
6344 KB |
Output is correct |
8 |
Correct |
9 ms |
6484 KB |
Output is correct |
9 |
Correct |
13 ms |
6484 KB |
Output is correct |
10 |
Correct |
11 ms |
6564 KB |
Output is correct |
11 |
Correct |
10 ms |
6576 KB |
Output is correct |
12 |
Correct |
9 ms |
6548 KB |
Output is correct |
13 |
Correct |
10 ms |
6612 KB |
Output is correct |
14 |
Correct |
10 ms |
6600 KB |
Output is correct |
15 |
Correct |
10 ms |
6564 KB |
Output is correct |
16 |
Correct |
10 ms |
6484 KB |
Output is correct |
17 |
Correct |
10 ms |
6552 KB |
Output is correct |
18 |
Correct |
10 ms |
6564 KB |
Output is correct |
19 |
Correct |
8 ms |
6484 KB |
Output is correct |
20 |
Correct |
8 ms |
6484 KB |
Output is correct |
21 |
Correct |
9 ms |
6484 KB |
Output is correct |
22 |
Correct |
11 ms |
6484 KB |
Output is correct |
23 |
Correct |
9 ms |
6556 KB |
Output is correct |
24 |
Correct |
10 ms |
6552 KB |
Output is correct |
25 |
Correct |
9 ms |
6540 KB |
Output is correct |
26 |
Correct |
9 ms |
6484 KB |
Output is correct |
27 |
Correct |
9 ms |
6556 KB |
Output is correct |
28 |
Correct |
11 ms |
6488 KB |
Output is correct |
29 |
Correct |
9 ms |
6560 KB |
Output is correct |
30 |
Correct |
9 ms |
6484 KB |
Output is correct |
31 |
Correct |
10 ms |
6468 KB |
Output is correct |
32 |
Correct |
9 ms |
6484 KB |
Output is correct |
33 |
Correct |
10 ms |
6612 KB |
Output is correct |
34 |
Correct |
12 ms |
6624 KB |
Output is correct |
35 |
Correct |
10 ms |
6632 KB |
Output is correct |
36 |
Correct |
3 ms |
5820 KB |
Output is correct |
37 |
Correct |
10 ms |
6548 KB |
Output is correct |
38 |
Correct |
9 ms |
6484 KB |
Output is correct |
39 |
Correct |
9 ms |
6552 KB |
Output is correct |
40 |
Correct |
514 ms |
37596 KB |
Output is correct |
41 |
Correct |
676 ms |
32464 KB |
Output is correct |
42 |
Correct |
638 ms |
35544 KB |
Output is correct |
43 |
Correct |
449 ms |
34388 KB |
Output is correct |
44 |
Correct |
467 ms |
33824 KB |
Output is correct |
45 |
Correct |
725 ms |
41076 KB |
Output is correct |
46 |
Correct |
721 ms |
41136 KB |
Output is correct |
47 |
Correct |
729 ms |
41176 KB |
Output is correct |
48 |
Correct |
751 ms |
41124 KB |
Output is correct |
49 |
Correct |
718 ms |
41084 KB |
Output is correct |
50 |
Correct |
780 ms |
44888 KB |
Output is correct |
51 |
Correct |
879 ms |
45288 KB |
Output is correct |
52 |
Correct |
853 ms |
44684 KB |
Output is correct |
53 |
Correct |
777 ms |
40728 KB |
Output is correct |
54 |
Correct |
763 ms |
40580 KB |
Output is correct |
55 |
Correct |
779 ms |
40716 KB |
Output is correct |
56 |
Correct |
634 ms |
41148 KB |
Output is correct |
57 |
Correct |
609 ms |
41144 KB |
Output is correct |
58 |
Correct |
603 ms |
41136 KB |
Output is correct |
59 |
Correct |
658 ms |
41148 KB |
Output is correct |
60 |
Correct |
647 ms |
41324 KB |
Output is correct |
61 |
Correct |
640 ms |
41212 KB |
Output is correct |
62 |
Correct |
633 ms |
41208 KB |
Output is correct |
63 |
Correct |
612 ms |
41076 KB |
Output is correct |
64 |
Correct |
652 ms |
41036 KB |
Output is correct |
65 |
Correct |
611 ms |
41084 KB |
Output is correct |
66 |
Correct |
596 ms |
41088 KB |
Output is correct |
67 |
Correct |
3 ms |
5844 KB |
Output is correct |
68 |
Correct |
10 ms |
6612 KB |
Output is correct |
69 |
Correct |
10 ms |
6612 KB |
Output is correct |
70 |
Correct |
12 ms |
6552 KB |
Output is correct |
71 |
Correct |
483 ms |
40480 KB |
Output is correct |
72 |
Correct |
506 ms |
43852 KB |
Output is correct |
73 |
Correct |
654 ms |
36140 KB |
Output is correct |
74 |
Correct |
810 ms |
51028 KB |
Output is correct |
75 |
Correct |
792 ms |
51028 KB |
Output is correct |
76 |
Correct |
775 ms |
51024 KB |
Output is correct |
77 |
Correct |
677 ms |
51052 KB |
Output is correct |
78 |
Correct |
664 ms |
51184 KB |
Output is correct |
79 |
Correct |
660 ms |
51184 KB |
Output is correct |
80 |
Correct |
615 ms |
51064 KB |
Output is correct |
81 |
Correct |
611 ms |
50900 KB |
Output is correct |
82 |
Correct |
710 ms |
51180 KB |
Output is correct |
83 |
Correct |
684 ms |
51044 KB |
Output is correct |
84 |
Correct |
567 ms |
38012 KB |
Output is correct |
85 |
Correct |
613 ms |
31540 KB |
Output is correct |
86 |
Correct |
502 ms |
30784 KB |
Output is correct |
87 |
Correct |
778 ms |
46188 KB |
Output is correct |
88 |
Correct |
789 ms |
46204 KB |
Output is correct |
89 |
Correct |
827 ms |
46200 KB |
Output is correct |
90 |
Correct |
769 ms |
46196 KB |
Output is correct |
91 |
Correct |
776 ms |
46220 KB |
Output is correct |
92 |
Correct |
901 ms |
49248 KB |
Output is correct |
93 |
Correct |
827 ms |
50260 KB |
Output is correct |
94 |
Correct |
844 ms |
46184 KB |
Output is correct |
95 |
Correct |
799 ms |
46192 KB |
Output is correct |
96 |
Correct |
851 ms |
46176 KB |
Output is correct |
97 |
Correct |
827 ms |
46164 KB |
Output is correct |
98 |
Correct |
658 ms |
45860 KB |
Output is correct |
99 |
Correct |
643 ms |
45736 KB |
Output is correct |
100 |
Correct |
705 ms |
45832 KB |
Output is correct |
101 |
Correct |
660 ms |
45904 KB |
Output is correct |
102 |
Correct |
679 ms |
46648 KB |
Output is correct |
103 |
Correct |
640 ms |
46628 KB |
Output is correct |
104 |
Correct |
689 ms |
46616 KB |
Output is correct |
105 |
Correct |
692 ms |
46228 KB |
Output is correct |
106 |
Correct |
642 ms |
46232 KB |
Output is correct |
107 |
Correct |
630 ms |
46156 KB |
Output is correct |
108 |
Correct |
615 ms |
46168 KB |
Output is correct |