#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using pli=pair<ll, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second
inline pli add(pli p1, pli p2){
return {p1.F+p2.F, p1.S+p2.S};
}
struct Vertex{
pli sum;
Vertex *l, *r;
Vertex(pli value={0, 0}) : sum(value), l(NULL), r(NULL) {}
Vertex(Vertex* l1, Vertex* r1) : sum(add(l1->sum, r1->sum)), l(l1), r(r1) {}
};
const int MAXN=100010, LOG=19;
int n, m, q, order[MAXN], tin[MAXN], tout[MAXN], assi[MAXN], up[LOG][MAXN], dep[MAXN], tim;
pii ch[MAXN];
vector<pii> g[MAXN];
Vertex* roots[MAXN];
Vertex* build(int tl, int tr){
if(tl==tr) return new Vertex();
int tm=(tl+tr)>>1;
return new Vertex(build(tl, tm), build(tm+1, tr));
}
pli sum(Vertex* v, int tl, int tr, int l, int r){
if(r<l) return {0, 0};
if(l==tl && r==tr) return v->sum;
int tm=(tl+tr)>>1;
return add(sum(v->l, tl, tm, l, min(r, tm)), sum(v->r, tm+1, tr, max(l, tm+1), r));
}
Vertex* update(Vertex* v, int tl, int tr, int pos, pli value){
if(tl==tr){
assert(tl==pos);
return new Vertex(add(v->sum, value));
}
int tm=(tl+tr)/2;
if(pos<=tm) return new Vertex(update(v->l, tl, tm, pos, value), v->r);
else return new Vertex(v->l, update(v->r, tm+1, tr, pos, value));
}
void dfs(int v, int p){
up[0][v]=p;
order[tim]=v;
tin[v]=tim++;
for(pii to:g[v]){
if(to.F==p) assi[to.S]=v;
else dep[to.F]=dep[v]+1, dfs(to.F, v);
}
tout[v]=tim;
}
int lca(int a, int b){
if(dep[a]<dep[b]) swap(a, b);
dforn(i, LOG) if(dep[a]-(1<<i)>=dep[b]) a=up[i][a];
dforn(i, LOG) if(up[i][a]!=up[i][b]) a=up[i][a], b=up[i][b];
return a==b? a : up[0][a];
}
pli query(Vertex* v, int a, int b){
int lc=lca(a, b);
return add(sum(v, 0, n, tin[lc]+1, tin[a]), sum(v, 0, n, tin[lc]+1, tin[b]));
}
int main(){
scanf("%d %d %d", &n, &m, &q);
forn(i, n-1){
int a, b; scanf("%d %d", &a, &b); --a, --b;
g[a].PB({b, i}), g[b].PB({a, i});
}
forn(i, m) scanf("%d %d", &ch[i].S, &ch[i].F), --ch[i].S;
sort(ch, ch+m);
dfs(0, 0);
forn(i, LOG-1) forn(j, n) up[i+1][j]=up[i][up[i][j]];
roots[0]=build(0, n);
forn(i, m){
Vertex* cur=roots[i];
int v=assi[ch[i].S];
cur=update(cur, 0, n, tin[v], {ch[i].F, 1});
cur=update(cur, 0, n, tout[v], {-ch[i].F, -1});
roots[i+1]=cur;
}
forn(i, q){
int s, t, x; ll y; scanf("%d %d %d %lld", &s, &t, &x, &y); --s, --t;
int lo=0, hi=m+1, best=0;
while(hi-lo>1){
int mid=(hi+lo)>>1;
pli cost = query(roots[mid], s, t);
if(cost.F<=y){
lo=mid;
best=max(best, cost.S);
}
else hi=mid;
}
int used=query(roots[m], s, t).S-best;
if(used<=x) printf("%d\n", x-used);
else printf("-1\n");
}
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:81:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | int a, b; scanf("%d %d", &a, &b); --a, --b;
| ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:84:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | forn(i, m) scanf("%d %d", &ch[i].S, &ch[i].F), --ch[i].S;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:97:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | int s, t, x; ll y; scanf("%d %d %d %lld", &s, &t, &x, &y); --s, --t;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
2 ms |
2664 KB |
Output is correct |
5 |
Correct |
13 ms |
5360 KB |
Output is correct |
6 |
Correct |
19 ms |
5332 KB |
Output is correct |
7 |
Correct |
15 ms |
4652 KB |
Output is correct |
8 |
Correct |
17 ms |
5564 KB |
Output is correct |
9 |
Correct |
29 ms |
5460 KB |
Output is correct |
10 |
Correct |
20 ms |
5560 KB |
Output is correct |
11 |
Correct |
26 ms |
5536 KB |
Output is correct |
12 |
Correct |
19 ms |
5560 KB |
Output is correct |
13 |
Correct |
14 ms |
5576 KB |
Output is correct |
14 |
Correct |
16 ms |
5460 KB |
Output is correct |
15 |
Correct |
15 ms |
5580 KB |
Output is correct |
16 |
Correct |
27 ms |
5500 KB |
Output is correct |
17 |
Correct |
18 ms |
5568 KB |
Output is correct |
18 |
Correct |
17 ms |
5588 KB |
Output is correct |
19 |
Correct |
24 ms |
5536 KB |
Output is correct |
20 |
Correct |
19 ms |
5536 KB |
Output is correct |
21 |
Correct |
17 ms |
5460 KB |
Output is correct |
22 |
Correct |
25 ms |
5532 KB |
Output is correct |
23 |
Correct |
15 ms |
5568 KB |
Output is correct |
24 |
Correct |
18 ms |
5508 KB |
Output is correct |
25 |
Correct |
16 ms |
5460 KB |
Output is correct |
26 |
Correct |
16 ms |
5460 KB |
Output is correct |
27 |
Correct |
20 ms |
5460 KB |
Output is correct |
28 |
Correct |
16 ms |
5556 KB |
Output is correct |
29 |
Correct |
12 ms |
5524 KB |
Output is correct |
30 |
Correct |
18 ms |
5508 KB |
Output is correct |
31 |
Correct |
17 ms |
5460 KB |
Output is correct |
32 |
Correct |
17 ms |
5460 KB |
Output is correct |
33 |
Correct |
13 ms |
5504 KB |
Output is correct |
34 |
Correct |
17 ms |
5584 KB |
Output is correct |
35 |
Correct |
13 ms |
5584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2768 KB |
Output is correct |
2 |
Correct |
17 ms |
5544 KB |
Output is correct |
3 |
Correct |
17 ms |
5508 KB |
Output is correct |
4 |
Correct |
17 ms |
5516 KB |
Output is correct |
5 |
Correct |
1831 ms |
178572 KB |
Output is correct |
6 |
Correct |
2459 ms |
153256 KB |
Output is correct |
7 |
Correct |
2380 ms |
132372 KB |
Output is correct |
8 |
Correct |
1755 ms |
128692 KB |
Output is correct |
9 |
Correct |
1570 ms |
137364 KB |
Output is correct |
10 |
Correct |
2925 ms |
195592 KB |
Output is correct |
11 |
Correct |
2980 ms |
195696 KB |
Output is correct |
12 |
Correct |
2827 ms |
195624 KB |
Output is correct |
13 |
Correct |
2909 ms |
195860 KB |
Output is correct |
14 |
Correct |
2913 ms |
195768 KB |
Output is correct |
15 |
Correct |
2680 ms |
202016 KB |
Output is correct |
16 |
Correct |
2520 ms |
202716 KB |
Output is correct |
17 |
Correct |
2565 ms |
198084 KB |
Output is correct |
18 |
Correct |
3123 ms |
195128 KB |
Output is correct |
19 |
Correct |
3117 ms |
195112 KB |
Output is correct |
20 |
Correct |
3253 ms |
195284 KB |
Output is correct |
21 |
Correct |
2133 ms |
195652 KB |
Output is correct |
22 |
Correct |
1871 ms |
194800 KB |
Output is correct |
23 |
Correct |
1999 ms |
194948 KB |
Output is correct |
24 |
Correct |
2013 ms |
194940 KB |
Output is correct |
25 |
Correct |
2073 ms |
196280 KB |
Output is correct |
26 |
Correct |
2083 ms |
194004 KB |
Output is correct |
27 |
Correct |
1888 ms |
194012 KB |
Output is correct |
28 |
Correct |
1258 ms |
194708 KB |
Output is correct |
29 |
Correct |
1407 ms |
194732 KB |
Output is correct |
30 |
Correct |
1589 ms |
194784 KB |
Output is correct |
31 |
Correct |
1642 ms |
194784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
Output is correct |
2 |
Correct |
13 ms |
5588 KB |
Output is correct |
3 |
Correct |
12 ms |
5588 KB |
Output is correct |
4 |
Correct |
14 ms |
5588 KB |
Output is correct |
5 |
Correct |
1324 ms |
138128 KB |
Output is correct |
6 |
Correct |
1272 ms |
115056 KB |
Output is correct |
7 |
Correct |
1758 ms |
164292 KB |
Output is correct |
8 |
Correct |
2560 ms |
197356 KB |
Output is correct |
9 |
Correct |
2563 ms |
197324 KB |
Output is correct |
10 |
Correct |
2349 ms |
197312 KB |
Output is correct |
11 |
Correct |
1877 ms |
198224 KB |
Output is correct |
12 |
Correct |
1908 ms |
197956 KB |
Output is correct |
13 |
Correct |
1821 ms |
195696 KB |
Output is correct |
14 |
Correct |
1200 ms |
197260 KB |
Output is correct |
15 |
Correct |
1031 ms |
197196 KB |
Output is correct |
16 |
Correct |
1368 ms |
197516 KB |
Output is correct |
17 |
Correct |
1359 ms |
197492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Correct |
2 ms |
2664 KB |
Output is correct |
5 |
Correct |
13 ms |
5360 KB |
Output is correct |
6 |
Correct |
19 ms |
5332 KB |
Output is correct |
7 |
Correct |
15 ms |
4652 KB |
Output is correct |
8 |
Correct |
17 ms |
5564 KB |
Output is correct |
9 |
Correct |
29 ms |
5460 KB |
Output is correct |
10 |
Correct |
20 ms |
5560 KB |
Output is correct |
11 |
Correct |
26 ms |
5536 KB |
Output is correct |
12 |
Correct |
19 ms |
5560 KB |
Output is correct |
13 |
Correct |
14 ms |
5576 KB |
Output is correct |
14 |
Correct |
16 ms |
5460 KB |
Output is correct |
15 |
Correct |
15 ms |
5580 KB |
Output is correct |
16 |
Correct |
27 ms |
5500 KB |
Output is correct |
17 |
Correct |
18 ms |
5568 KB |
Output is correct |
18 |
Correct |
17 ms |
5588 KB |
Output is correct |
19 |
Correct |
24 ms |
5536 KB |
Output is correct |
20 |
Correct |
19 ms |
5536 KB |
Output is correct |
21 |
Correct |
17 ms |
5460 KB |
Output is correct |
22 |
Correct |
25 ms |
5532 KB |
Output is correct |
23 |
Correct |
15 ms |
5568 KB |
Output is correct |
24 |
Correct |
18 ms |
5508 KB |
Output is correct |
25 |
Correct |
16 ms |
5460 KB |
Output is correct |
26 |
Correct |
16 ms |
5460 KB |
Output is correct |
27 |
Correct |
20 ms |
5460 KB |
Output is correct |
28 |
Correct |
16 ms |
5556 KB |
Output is correct |
29 |
Correct |
12 ms |
5524 KB |
Output is correct |
30 |
Correct |
18 ms |
5508 KB |
Output is correct |
31 |
Correct |
17 ms |
5460 KB |
Output is correct |
32 |
Correct |
17 ms |
5460 KB |
Output is correct |
33 |
Correct |
13 ms |
5504 KB |
Output is correct |
34 |
Correct |
17 ms |
5584 KB |
Output is correct |
35 |
Correct |
13 ms |
5584 KB |
Output is correct |
36 |
Correct |
2 ms |
2768 KB |
Output is correct |
37 |
Correct |
17 ms |
5544 KB |
Output is correct |
38 |
Correct |
17 ms |
5508 KB |
Output is correct |
39 |
Correct |
17 ms |
5516 KB |
Output is correct |
40 |
Correct |
1831 ms |
178572 KB |
Output is correct |
41 |
Correct |
2459 ms |
153256 KB |
Output is correct |
42 |
Correct |
2380 ms |
132372 KB |
Output is correct |
43 |
Correct |
1755 ms |
128692 KB |
Output is correct |
44 |
Correct |
1570 ms |
137364 KB |
Output is correct |
45 |
Correct |
2925 ms |
195592 KB |
Output is correct |
46 |
Correct |
2980 ms |
195696 KB |
Output is correct |
47 |
Correct |
2827 ms |
195624 KB |
Output is correct |
48 |
Correct |
2909 ms |
195860 KB |
Output is correct |
49 |
Correct |
2913 ms |
195768 KB |
Output is correct |
50 |
Correct |
2680 ms |
202016 KB |
Output is correct |
51 |
Correct |
2520 ms |
202716 KB |
Output is correct |
52 |
Correct |
2565 ms |
198084 KB |
Output is correct |
53 |
Correct |
3123 ms |
195128 KB |
Output is correct |
54 |
Correct |
3117 ms |
195112 KB |
Output is correct |
55 |
Correct |
3253 ms |
195284 KB |
Output is correct |
56 |
Correct |
2133 ms |
195652 KB |
Output is correct |
57 |
Correct |
1871 ms |
194800 KB |
Output is correct |
58 |
Correct |
1999 ms |
194948 KB |
Output is correct |
59 |
Correct |
2013 ms |
194940 KB |
Output is correct |
60 |
Correct |
2073 ms |
196280 KB |
Output is correct |
61 |
Correct |
2083 ms |
194004 KB |
Output is correct |
62 |
Correct |
1888 ms |
194012 KB |
Output is correct |
63 |
Correct |
1258 ms |
194708 KB |
Output is correct |
64 |
Correct |
1407 ms |
194732 KB |
Output is correct |
65 |
Correct |
1589 ms |
194784 KB |
Output is correct |
66 |
Correct |
1642 ms |
194784 KB |
Output is correct |
67 |
Correct |
2 ms |
2772 KB |
Output is correct |
68 |
Correct |
13 ms |
5588 KB |
Output is correct |
69 |
Correct |
12 ms |
5588 KB |
Output is correct |
70 |
Correct |
14 ms |
5588 KB |
Output is correct |
71 |
Correct |
1324 ms |
138128 KB |
Output is correct |
72 |
Correct |
1272 ms |
115056 KB |
Output is correct |
73 |
Correct |
1758 ms |
164292 KB |
Output is correct |
74 |
Correct |
2560 ms |
197356 KB |
Output is correct |
75 |
Correct |
2563 ms |
197324 KB |
Output is correct |
76 |
Correct |
2349 ms |
197312 KB |
Output is correct |
77 |
Correct |
1877 ms |
198224 KB |
Output is correct |
78 |
Correct |
1908 ms |
197956 KB |
Output is correct |
79 |
Correct |
1821 ms |
195696 KB |
Output is correct |
80 |
Correct |
1200 ms |
197260 KB |
Output is correct |
81 |
Correct |
1031 ms |
197196 KB |
Output is correct |
82 |
Correct |
1368 ms |
197516 KB |
Output is correct |
83 |
Correct |
1359 ms |
197492 KB |
Output is correct |
84 |
Correct |
1805 ms |
177452 KB |
Output is correct |
85 |
Correct |
1969 ms |
151468 KB |
Output is correct |
86 |
Correct |
1827 ms |
109608 KB |
Output is correct |
87 |
Correct |
3082 ms |
194640 KB |
Output is correct |
88 |
Correct |
2913 ms |
194596 KB |
Output is correct |
89 |
Correct |
2961 ms |
194924 KB |
Output is correct |
90 |
Correct |
2960 ms |
194860 KB |
Output is correct |
91 |
Correct |
2898 ms |
194652 KB |
Output is correct |
92 |
Correct |
2724 ms |
196804 KB |
Output is correct |
93 |
Correct |
2635 ms |
196408 KB |
Output is correct |
94 |
Correct |
3072 ms |
194348 KB |
Output is correct |
95 |
Correct |
3087 ms |
194348 KB |
Output is correct |
96 |
Correct |
3261 ms |
194256 KB |
Output is correct |
97 |
Correct |
3325 ms |
194456 KB |
Output is correct |
98 |
Correct |
2857 ms |
194900 KB |
Output is correct |
99 |
Correct |
2891 ms |
194732 KB |
Output is correct |
100 |
Correct |
3023 ms |
194824 KB |
Output is correct |
101 |
Correct |
2955 ms |
195072 KB |
Output is correct |
102 |
Correct |
2416 ms |
194000 KB |
Output is correct |
103 |
Correct |
2359 ms |
193948 KB |
Output is correct |
104 |
Correct |
2419 ms |
193948 KB |
Output is correct |
105 |
Correct |
1522 ms |
194816 KB |
Output is correct |
106 |
Correct |
1345 ms |
194668 KB |
Output is correct |
107 |
Correct |
1464 ms |
194988 KB |
Output is correct |
108 |
Correct |
1611 ms |
194648 KB |
Output is correct |