#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
struct node {
long long val;
int cnt;
node *left, *right;
node(long long val, int cnt, node* left, node *right) : val(val), cnt(cnt), left(left), right(right) {};
};
node *perstree[100001];
int in[100001];
int out[100001];
int height[100001];
int bl[100001][20];
pair<int,int> edges[100001];
vector<pair<int,int>> graph[100001];
vector<pair<int,int>> vctr;
int n;
int total[100001];
int borders[100001];
long long getval(node *n) {
if (n)return n->val;
else return 0;
}
int getcnt(node *n) {
if (n)return n->cnt;
else return 0;
}
node* build(int a, int b) {
if (a > b)return NULL;
if (a == b) {
return new node(0,0,NULL,NULL);
}
return new node(0,0,build(a,(a+b)/2),build((a+b)/2+1,b));
}
node* update(node *n, int a, int b, int x, long long v, int c) {
// printf("%d %d %d %lld\n",a,b,x,v);
if (a > b)return NULL;
if (a == b) {
// printf("%d : %lld + %lld , %d + %d\n",a,n->val,v,n->cnt,c);
return new node(n->val+v,n->cnt+c,NULL,NULL);
}
node* nleft;
node* nright;
if (x <= (a+b)/2) {
nleft = update(n->left,a,(a+b)/2,x,v,c);
nright = n->right;
} else if (x >= (a+b)/2+1) {
nright = update(n->right,(a+b)/2+1,b,x,v,c);
nleft = n->left;
}
// printf("%d-%d : %lld -> %lld , %d -> %d\n",a,b,n->val,getval(nleft)+getval(nright),n->cnt,getcnt(nleft)+getcnt(nright));
return new node(getval(nleft)+getval(nright),getcnt(nleft)+getcnt(nright),nleft,nright);
}
pair<long long,int> query(node *n, int a, int b, int x, int y) {
if (a > b || b < x || y < a)return {0,0};
if (x <= a && b <= y) {
// printf("%d=%d : %lld , %d\n",a,b,n->val,n->cnt);
return {n->val,n->cnt};
}
pair<long long,int> qleft, qright;
if (y <= (a+b)/2) {
qleft = query(n->left,a,(a+b)/2,x,y);
qright = {0,0};
} else if (x >= (a+b)/2+1) {
qright = query(n->right,(a+b)/2+1,b,x,y);
qleft = {0,0};
} else {
qleft = query(n->left,a,(a+b)/2,x,y);
qright = query(n->right,(a+b)/2+1,b,x,y);
}
// printf("%d==%d %d %d: %lld , %d\n",a,b,x,y,qleft.f+qright.f,qleft.s+qright.s);
return {qleft.f+qright.f,qleft.s+qright.s};
}
void findsize(int node, int pa, int h) {
height[node] = h;
if (pa != -1) {
bl[node][0] = pa;
}
if (pa != -1)bl[node][0] = pa;
for (auto it : graph[node]) {
if (it.f == pa)continue;
findsize(it.f,node,h+1);
}
return;
}
void findborders(int node, int pa, int b) {
total[node] = b;
for (auto it : graph[node]) {
if (it.f == pa)continue;
findborders(it.f,node,b+borders[it.f]);
}
return;
}
int timer = 1;
void eulertour(int node, int pa) {
in[node] = timer;
++timer;
for (auto it : graph[node]) {
if (it.f == pa) {
edges[it.s] = {it.f,node};
continue;
}
eulertour(it.f,node);
}
out[node] = timer;
return;
}
int findlca(int a, int b) {
if (height[a] != height[b]) {
if (height[b] < height[a]) {
swap(a,b);
}
for (int dist = height[b]-height[a]; dist > 0; dist -= dist&-dist) {
b = bl[b][(int)log2(dist&-dist)];
}
}
int cap1 = floor(log2(n));
for (;a != b;) {
int l = -1;
int r = cap1;
for (;;) {
if (l >= r)break;
int m = (l+r+1)/2;
if (bl[a][m] == bl[b][m]) {
r = m-1;
} else {
l = m;
}
}
if (l == -1) {
l = 0;
}
a = bl[a][l];
b = bl[b][l];
cap1 = l-1;
}
return a;
}
pair<long long,int> path(int amt, int u, int v, int lca) {
pair<long long,int> qu, qv, qlca;
qu = query(perstree[amt],1,n+1,1,in[u]);
qv = query(perstree[amt],1,n+1,1,in[v]);
qlca = query(perstree[amt],1,n+1,1,in[lca]);
// printf("%lld %d %lld %d %lld %d\n",qu.f,qu.s,qv.f,qv.s,qlca.f,qlca.s);
return {qu.f+qv.f-2*qlca.f,qu.s+qv.s-2*qlca.s};
}
int tcoins(int u, int v, int lca) {
return total[u]+total[v]-2*total[lca];
}
int main() {
int m, q;
scanf("%d%d%d",&n,&m,&q);
for (int i = 1; i <= n-1; ++i) {
int a, b;
scanf("%d%d",&a,&b);
graph[a].push_back({b,i});
graph[b].push_back({a,i});
}
for (int i = 0; i < m; ++i) {
int p, c;
scanf("%d%d",&p,&c);
vctr.push_back({c,p});
}
vctr.push_back({-1,-1});
sort(vctr.begin(),vctr.end());
findsize(1,-1,0);
eulertour(1,-1);
for (auto it : vctr) {
++borders[edges[it.s].s];
// printf("added %d\n",edges[it.s].s);
}
findborders(1,-1,0);
// for (int i = 1; i <= n; ++i) {
// printf("%d -> %d\n",in[i],out[i]);
// }
// for (int j = 1; j <= n; ++j) {
// printf("%d ",total[j]);
// }
// printf("\n");
for (int k = 1; k <= 19; ++k) {
for (int i = 1; i <= n; ++i) {
bl[i][k] = bl[bl[i][k-1]][k-1];
}
}
perstree[0] = build(1,n+1);
// for (int j = 1; j <= n; ++j) {
// printf("[%lld] ",query(perstree[0],1,n+1,1,in[j]).f);
// }
// printf("\n\n");
for (int i = 1; i <= m; ++i) {
// printf("%d %d : %d %d\n",edges[vctr[i].s].s,in[edges[vctr[i].s].s],edges[vctr[i].s].f,out[edges[vctr[i].s].s]);
perstree[i] = update(perstree[i-1],1,n+1,in[edges[vctr[i].s].s],vctr[i].f,1);
perstree[i] = update(perstree[i],1,n+1,out[edges[vctr[i].s].s],-vctr[i].f,-1);
for (int j = 1; j <= n; ++j) {
// printf("[%lld] ",query(perstree[i],1,n+1,1,in[j]).f);
}
// printf("\n\n");
}
// for (int i = 0; i <= m; ++i) {
// for (int j = 1; j <= n; ++j) {
// printf("%lld ",query(perstree[i],1,n+1,1,in[j]).f);
// }
// printf("\n");
// }
for (int qi = 0; qi < q; ++qi) {
int s, t, x;
long long y;
scanf("%d%d%d%lld",&s,&t,&x,&y);
int l = 0, r = m;
int lca = findlca(s,t);
// printf("\n%d %d lca: %d\n",s,t,lca);
while (true) {
if (l >= r)break;
int mid = (l+r+1)/2;
long long cost = path(mid,s,t,lca).f;
// printf("%d %lld\n",mid,cost);
if (cost <= y) {
l = mid;
} else {
r = mid-1;
}
}
// printf("%d !\n\n",l);
int coins = path(l,s,t,lca).s;
int totalcoins = tcoins(s,t,lca);
int pay = totalcoins-coins;
// printf("%d %d %d\n",coins,totalcoins,pay);
if (pay <= x) {
printf("%d\n",x-pay);
} else {
printf("-1\n");
}
}
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | scanf("%d%d%d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:171:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
currencies.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
177 | scanf("%d%d",&p,&c);
| ~~~~~^~~~~~~~~~~~~~
currencies.cpp:224:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
224 | scanf("%d%d%d%lld",&s,&t,&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
7 ms |
8916 KB |
Output is correct |
6 |
Correct |
8 ms |
9052 KB |
Output is correct |
7 |
Correct |
8 ms |
8284 KB |
Output is correct |
8 |
Correct |
9 ms |
9052 KB |
Output is correct |
9 |
Correct |
9 ms |
9052 KB |
Output is correct |
10 |
Correct |
10 ms |
9052 KB |
Output is correct |
11 |
Correct |
10 ms |
9052 KB |
Output is correct |
12 |
Correct |
9 ms |
9052 KB |
Output is correct |
13 |
Correct |
9 ms |
9052 KB |
Output is correct |
14 |
Correct |
9 ms |
9052 KB |
Output is correct |
15 |
Correct |
11 ms |
9052 KB |
Output is correct |
16 |
Correct |
14 ms |
9052 KB |
Output is correct |
17 |
Correct |
9 ms |
9048 KB |
Output is correct |
18 |
Correct |
11 ms |
9048 KB |
Output is correct |
19 |
Correct |
9 ms |
9052 KB |
Output is correct |
20 |
Correct |
9 ms |
9048 KB |
Output is correct |
21 |
Correct |
9 ms |
9052 KB |
Output is correct |
22 |
Correct |
9 ms |
9052 KB |
Output is correct |
23 |
Correct |
9 ms |
9052 KB |
Output is correct |
24 |
Correct |
9 ms |
9268 KB |
Output is correct |
25 |
Correct |
9 ms |
9176 KB |
Output is correct |
26 |
Correct |
9 ms |
9052 KB |
Output is correct |
27 |
Correct |
9 ms |
9052 KB |
Output is correct |
28 |
Correct |
9 ms |
9168 KB |
Output is correct |
29 |
Correct |
9 ms |
9052 KB |
Output is correct |
30 |
Correct |
8 ms |
9052 KB |
Output is correct |
31 |
Correct |
9 ms |
9052 KB |
Output is correct |
32 |
Correct |
10 ms |
9308 KB |
Output is correct |
33 |
Correct |
9 ms |
9284 KB |
Output is correct |
34 |
Correct |
9 ms |
9052 KB |
Output is correct |
35 |
Correct |
9 ms |
9052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
9 ms |
9052 KB |
Output is correct |
3 |
Correct |
9 ms |
9052 KB |
Output is correct |
4 |
Correct |
9 ms |
9092 KB |
Output is correct |
5 |
Correct |
1106 ms |
181496 KB |
Output is correct |
6 |
Correct |
1448 ms |
159948 KB |
Output is correct |
7 |
Correct |
1398 ms |
137444 KB |
Output is correct |
8 |
Correct |
1014 ms |
132660 KB |
Output is correct |
9 |
Correct |
1018 ms |
140908 KB |
Output is correct |
10 |
Correct |
2071 ms |
199608 KB |
Output is correct |
11 |
Correct |
1973 ms |
199776 KB |
Output is correct |
12 |
Correct |
1906 ms |
199812 KB |
Output is correct |
13 |
Correct |
1986 ms |
199504 KB |
Output is correct |
14 |
Correct |
1956 ms |
199404 KB |
Output is correct |
15 |
Correct |
1985 ms |
206664 KB |
Output is correct |
16 |
Correct |
1983 ms |
207420 KB |
Output is correct |
17 |
Correct |
1979 ms |
203152 KB |
Output is correct |
18 |
Correct |
2226 ms |
199764 KB |
Output is correct |
19 |
Correct |
2190 ms |
199880 KB |
Output is correct |
20 |
Correct |
2182 ms |
199704 KB |
Output is correct |
21 |
Correct |
989 ms |
198988 KB |
Output is correct |
22 |
Correct |
1008 ms |
199408 KB |
Output is correct |
23 |
Correct |
1107 ms |
199324 KB |
Output is correct |
24 |
Correct |
1094 ms |
199764 KB |
Output is correct |
25 |
Correct |
1332 ms |
201368 KB |
Output is correct |
26 |
Correct |
1250 ms |
199012 KB |
Output is correct |
27 |
Correct |
1257 ms |
199264 KB |
Output is correct |
28 |
Correct |
714 ms |
199536 KB |
Output is correct |
29 |
Correct |
716 ms |
199592 KB |
Output is correct |
30 |
Correct |
979 ms |
199668 KB |
Output is correct |
31 |
Correct |
948 ms |
199600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
9 ms |
9116 KB |
Output is correct |
3 |
Correct |
9 ms |
9052 KB |
Output is correct |
4 |
Correct |
11 ms |
9052 KB |
Output is correct |
5 |
Correct |
1125 ms |
142852 KB |
Output is correct |
6 |
Correct |
1108 ms |
120020 KB |
Output is correct |
7 |
Correct |
1564 ms |
171224 KB |
Output is correct |
8 |
Correct |
2021 ms |
202960 KB |
Output is correct |
9 |
Correct |
2113 ms |
202456 KB |
Output is correct |
10 |
Correct |
2097 ms |
202768 KB |
Output is correct |
11 |
Correct |
1697 ms |
203536 KB |
Output is correct |
12 |
Correct |
1670 ms |
203724 KB |
Output is correct |
13 |
Correct |
1669 ms |
201404 KB |
Output is correct |
14 |
Correct |
1004 ms |
202588 KB |
Output is correct |
15 |
Correct |
939 ms |
202684 KB |
Output is correct |
16 |
Correct |
1236 ms |
202844 KB |
Output is correct |
17 |
Correct |
1245 ms |
202780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
7 ms |
8916 KB |
Output is correct |
6 |
Correct |
8 ms |
9052 KB |
Output is correct |
7 |
Correct |
8 ms |
8284 KB |
Output is correct |
8 |
Correct |
9 ms |
9052 KB |
Output is correct |
9 |
Correct |
9 ms |
9052 KB |
Output is correct |
10 |
Correct |
10 ms |
9052 KB |
Output is correct |
11 |
Correct |
10 ms |
9052 KB |
Output is correct |
12 |
Correct |
9 ms |
9052 KB |
Output is correct |
13 |
Correct |
9 ms |
9052 KB |
Output is correct |
14 |
Correct |
9 ms |
9052 KB |
Output is correct |
15 |
Correct |
11 ms |
9052 KB |
Output is correct |
16 |
Correct |
14 ms |
9052 KB |
Output is correct |
17 |
Correct |
9 ms |
9048 KB |
Output is correct |
18 |
Correct |
11 ms |
9048 KB |
Output is correct |
19 |
Correct |
9 ms |
9052 KB |
Output is correct |
20 |
Correct |
9 ms |
9048 KB |
Output is correct |
21 |
Correct |
9 ms |
9052 KB |
Output is correct |
22 |
Correct |
9 ms |
9052 KB |
Output is correct |
23 |
Correct |
9 ms |
9052 KB |
Output is correct |
24 |
Correct |
9 ms |
9268 KB |
Output is correct |
25 |
Correct |
9 ms |
9176 KB |
Output is correct |
26 |
Correct |
9 ms |
9052 KB |
Output is correct |
27 |
Correct |
9 ms |
9052 KB |
Output is correct |
28 |
Correct |
9 ms |
9168 KB |
Output is correct |
29 |
Correct |
9 ms |
9052 KB |
Output is correct |
30 |
Correct |
8 ms |
9052 KB |
Output is correct |
31 |
Correct |
9 ms |
9052 KB |
Output is correct |
32 |
Correct |
10 ms |
9308 KB |
Output is correct |
33 |
Correct |
9 ms |
9284 KB |
Output is correct |
34 |
Correct |
9 ms |
9052 KB |
Output is correct |
35 |
Correct |
9 ms |
9052 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
9 ms |
9052 KB |
Output is correct |
38 |
Correct |
9 ms |
9052 KB |
Output is correct |
39 |
Correct |
9 ms |
9092 KB |
Output is correct |
40 |
Correct |
1106 ms |
181496 KB |
Output is correct |
41 |
Correct |
1448 ms |
159948 KB |
Output is correct |
42 |
Correct |
1398 ms |
137444 KB |
Output is correct |
43 |
Correct |
1014 ms |
132660 KB |
Output is correct |
44 |
Correct |
1018 ms |
140908 KB |
Output is correct |
45 |
Correct |
2071 ms |
199608 KB |
Output is correct |
46 |
Correct |
1973 ms |
199776 KB |
Output is correct |
47 |
Correct |
1906 ms |
199812 KB |
Output is correct |
48 |
Correct |
1986 ms |
199504 KB |
Output is correct |
49 |
Correct |
1956 ms |
199404 KB |
Output is correct |
50 |
Correct |
1985 ms |
206664 KB |
Output is correct |
51 |
Correct |
1983 ms |
207420 KB |
Output is correct |
52 |
Correct |
1979 ms |
203152 KB |
Output is correct |
53 |
Correct |
2226 ms |
199764 KB |
Output is correct |
54 |
Correct |
2190 ms |
199880 KB |
Output is correct |
55 |
Correct |
2182 ms |
199704 KB |
Output is correct |
56 |
Correct |
989 ms |
198988 KB |
Output is correct |
57 |
Correct |
1008 ms |
199408 KB |
Output is correct |
58 |
Correct |
1107 ms |
199324 KB |
Output is correct |
59 |
Correct |
1094 ms |
199764 KB |
Output is correct |
60 |
Correct |
1332 ms |
201368 KB |
Output is correct |
61 |
Correct |
1250 ms |
199012 KB |
Output is correct |
62 |
Correct |
1257 ms |
199264 KB |
Output is correct |
63 |
Correct |
714 ms |
199536 KB |
Output is correct |
64 |
Correct |
716 ms |
199592 KB |
Output is correct |
65 |
Correct |
979 ms |
199668 KB |
Output is correct |
66 |
Correct |
948 ms |
199600 KB |
Output is correct |
67 |
Correct |
1 ms |
6492 KB |
Output is correct |
68 |
Correct |
9 ms |
9116 KB |
Output is correct |
69 |
Correct |
9 ms |
9052 KB |
Output is correct |
70 |
Correct |
11 ms |
9052 KB |
Output is correct |
71 |
Correct |
1125 ms |
142852 KB |
Output is correct |
72 |
Correct |
1108 ms |
120020 KB |
Output is correct |
73 |
Correct |
1564 ms |
171224 KB |
Output is correct |
74 |
Correct |
2021 ms |
202960 KB |
Output is correct |
75 |
Correct |
2113 ms |
202456 KB |
Output is correct |
76 |
Correct |
2097 ms |
202768 KB |
Output is correct |
77 |
Correct |
1697 ms |
203536 KB |
Output is correct |
78 |
Correct |
1670 ms |
203724 KB |
Output is correct |
79 |
Correct |
1669 ms |
201404 KB |
Output is correct |
80 |
Correct |
1004 ms |
202588 KB |
Output is correct |
81 |
Correct |
939 ms |
202684 KB |
Output is correct |
82 |
Correct |
1236 ms |
202844 KB |
Output is correct |
83 |
Correct |
1245 ms |
202780 KB |
Output is correct |
84 |
Correct |
1289 ms |
182720 KB |
Output is correct |
85 |
Correct |
1408 ms |
157280 KB |
Output is correct |
86 |
Correct |
1229 ms |
115424 KB |
Output is correct |
87 |
Correct |
2212 ms |
199548 KB |
Output is correct |
88 |
Correct |
2223 ms |
199800 KB |
Output is correct |
89 |
Correct |
2247 ms |
199704 KB |
Output is correct |
90 |
Correct |
2231 ms |
199508 KB |
Output is correct |
91 |
Correct |
2212 ms |
199364 KB |
Output is correct |
92 |
Correct |
2205 ms |
202128 KB |
Output is correct |
93 |
Correct |
2295 ms |
201620 KB |
Output is correct |
94 |
Correct |
2950 ms |
199560 KB |
Output is correct |
95 |
Correct |
2825 ms |
199428 KB |
Output is correct |
96 |
Correct |
2497 ms |
199400 KB |
Output is correct |
97 |
Correct |
2338 ms |
199604 KB |
Output is correct |
98 |
Correct |
1948 ms |
199644 KB |
Output is correct |
99 |
Correct |
1993 ms |
199252 KB |
Output is correct |
100 |
Correct |
1968 ms |
199456 KB |
Output is correct |
101 |
Correct |
1986 ms |
199536 KB |
Output is correct |
102 |
Correct |
1677 ms |
199176 KB |
Output is correct |
103 |
Correct |
1699 ms |
199104 KB |
Output is correct |
104 |
Correct |
1715 ms |
199260 KB |
Output is correct |
105 |
Correct |
886 ms |
199524 KB |
Output is correct |
106 |
Correct |
815 ms |
199364 KB |
Output is correct |
107 |
Correct |
959 ms |
199856 KB |
Output is correct |
108 |
Correct |
988 ms |
199368 KB |
Output is correct |