#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int mxs = 1e14;
int32_t n, m, q;
vector<int> adj[MAXN];
int st[MAXN], en[MAXN], cur = 0;
bool is[MAXN];
int cost[MAXN];
pair<int,int> anc[19][2*MAXN];
int dep[MAXN];
vector<int> euler;
int dfn[2*MAXN];
void dfs(int node, int prv) {
st[node] = ++cur;
dfn[cur] = node;
euler.push_back(node);
dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
for(int x: adj[node]) {
if(x != prv) {
dfs(x, node);
euler.push_back(node);
}
}
en[node] = ++cur;
dfn[cur] = node;
}
int ans[MAXN];
int block;
int32_t s[MAXN], t[MAXN], x[MAXN];
int y[MAXN], p[MAXN]; //lca
int mi[MAXN], ma[MAXN], ord[MAXN];
int l[MAXN], r[MAXN];
int lca(int u, int v) {
int m1 = min(mi[u], mi[v]), m2 = max(ma[u], ma[v]);
int k = 32 - __builtin_clz(m2-m1+1) - 1;
return min(anc[k][m1], anc[k][m2 - (1<<k) + 1]).second;
}
bool cmp(int qa, int qb) {
if(l[qa] / block != l[qb] / block) return l[qa] / block < l[qb] / block;
return r[qa] < r[qb];
}
pair<int,int> chkpt[MAXN];
int freq[MAXN];
int pos[MAXN];
int val[MAXN];
int sumblock[MAXN];
int cnt[MAXN];
inline void ins(int x) {
int pp = pos[x];
val[pp] = cost[x];
cnt[pp / block]++;
sumblock[pp / block] += cost[x];
}
inline void del(int x) {
int pp = pos[x];
val[pp] = 0;
cnt[pp / block]--;
sumblock[pp / block] -= cost[x];
}
inline void add(int x) {
x = dfn[x];
if(!is[x]) return;
freq[x]++;
if(freq[x] == 2) del(x);
else ins(x);
}
inline void sub(int x) {
x = dfn[x];
if(!is[x]) return;
freq[x]--;
if(freq[x] == 0) del(x);
else ins(x);
}
pair<int,int> sto[MAXN];
vector<int> stuff[MAXN];
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long x, long long y) {
long long u = uniform_int_distribution<long long>(x, y)(rng);
return u;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
scanf("%d %d %d", &n, &m, &q);
for(int i=0; i+1<n; i++) {
int32_t u, v;
scanf("%d %d", &u, &v);
sto[i] = {u, v};
}
int rt = rnd(1, n);
for(int i=0; i<m; i++) {
int32_t p, c;
scanf("%d %d", &p, &c);
n++;
p--;
stuff[p].push_back(n);
is[n] = 1;
cost[n] = c;
chkpt[i] = {c, n};
}
for(int i=0; i+1<n-m; i++) {
int u = sto[i].first;
int v = sto[i].second;
if(stuff[i].empty()) {
adj[u].push_back(v);
adj[v].push_back(u);
}
else {
adj[u].push_back(stuff[i][0]);
adj[stuff[i][0]].push_back(u);
for(int j=0; j+1<stuff[i].size(); j++) {
adj[stuff[i][j]].push_back(stuff[i][j+1]);
adj[stuff[i][j+1]].push_back(stuff[i][j]);
}
int fin = stuff[i].size() - 1;
adj[stuff[i][fin]].push_back(v);
adj[v].push_back(stuff[i][fin]);
}
}
block = ceil(sqrt(n)) * 2;
sort(chkpt, chkpt + m);
for(int i=0; i<m; i++) pos[chkpt[i].second] = i;
dfs(rt, -1);
for(int i=0; i<euler.size(); i++) anc[0][i] = {dep[euler[i]], euler[i]};
for(int i=0; i<euler.size(); i++) ma[euler[i]] = i;
for(int i=euler.size()-1; i>=0; i--) mi[euler[i]] = i;
for(int i=1; i<19; i++) {
for(int j=0; j+(1<<i)-1<euler.size(); j++) {
anc[i][j] = min(anc[i-1][j], anc[i-1][j+(1<<(i-1))]);
}
}
for(int i=1; i<=q; i++) {
scanf("%d %d %d %lld", &s[i], &t[i], &x[i], &y[i]);
if(st[s[i]] > st[t[i]]) swap(s[i], t[i]);
p[i] = lca(s[i], t[i]);
if(s[i] == p[i]) l[i] = st[s[i]], r[i] = st[t[i]];
else l[i] = en[s[i]], r[i] = st[t[i]];
}
for(int i=1; i<=q; i++) ord[i] = i;
sort(ord+1, ord+q+1, cmp);
block = ceil(sqrt(m));
int lprev = 0, rprev = 0;
for(int i=1; i<=q; i++) {
int idx = ord[i];
int lnew = l[idx], rnew = r[idx];
while(rprev < rnew) {
rprev++; add(rprev);
}
while(lprev > lnew) {
lprev--; add(lprev);
}
while(rprev > rnew) {
sub(rprev); rprev--;
}
while(lprev < lnew) {
sub(lprev); lprev++;
}
int run = 0; // number of checkpoints payable using silver
int gold = x[idx], silver = y[idx];
if(silver >= mxs) {
ans[idx] = gold;
continue;
}
int tcc = 0;
bool pk = 0;
for(int j=0; j<block; j++) {
tcc += cnt[j];
if(pk)continue;
if(sumblock[j] <= silver) {
silver -= sumblock[j];
run += cnt[j];
}
else {
int mlm = min((int) m, (j+1) * block);
for(int k=j*block; k<mlm; k++) {
if(val[k] <= silver && val[k] > 0) {
silver -= val[k];
run++;
}
}
pk = 1;
}
}
gold -= (tcc - run);
gold = max(gold, -1ll);
ans[idx] = gold;
}
for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}
/*
4 6 1
1 2
2 3
1 4
2 1
4 1
3 5
3 2
4 2
3 2
1 4 2 6
*/
Compilation message
currencies.cpp: In function 'int32_t main()':
currencies.cpp:115:23: 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]
115 | for(int j=0; j+1<stuff[i].size(); j++) {
| ~~~^~~~~~~~~~~~~~~~
currencies.cpp:128:17: 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]
128 | for(int i=0; i<euler.size(); i++) anc[0][i] = {dep[euler[i]], euler[i]};
| ~^~~~~~~~~~~~~
currencies.cpp:129:17: 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]
129 | for(int i=0; i<euler.size(); i++) ma[euler[i]] = i;
| ~^~~~~~~~~~~~~
currencies.cpp:132:28: 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]
132 | for(int j=0; j+(1<<i)-1<euler.size(); j++) {
| ~~~~~~~~~~^~~~~~~~~~~~~
currencies.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d %d", &p, &c);
| ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d %d %d %lld", &s[i], &t[i], &x[i], &y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9856 KB |
Output is correct |
2 |
Correct |
5 ms |
9812 KB |
Output is correct |
3 |
Correct |
6 ms |
9812 KB |
Output is correct |
4 |
Correct |
6 ms |
9900 KB |
Output is correct |
5 |
Correct |
13 ms |
12076 KB |
Output is correct |
6 |
Correct |
14 ms |
12228 KB |
Output is correct |
7 |
Correct |
12 ms |
11556 KB |
Output is correct |
8 |
Correct |
16 ms |
12328 KB |
Output is correct |
9 |
Correct |
17 ms |
12244 KB |
Output is correct |
10 |
Correct |
15 ms |
12244 KB |
Output is correct |
11 |
Correct |
14 ms |
12332 KB |
Output is correct |
12 |
Correct |
14 ms |
12244 KB |
Output is correct |
13 |
Correct |
15 ms |
12452 KB |
Output is correct |
14 |
Correct |
15 ms |
12448 KB |
Output is correct |
15 |
Correct |
13 ms |
12360 KB |
Output is correct |
16 |
Correct |
16 ms |
12392 KB |
Output is correct |
17 |
Correct |
14 ms |
12328 KB |
Output is correct |
18 |
Correct |
16 ms |
12324 KB |
Output is correct |
19 |
Correct |
15 ms |
12244 KB |
Output is correct |
20 |
Correct |
13 ms |
12328 KB |
Output is correct |
21 |
Correct |
14 ms |
12320 KB |
Output is correct |
22 |
Correct |
14 ms |
12244 KB |
Output is correct |
23 |
Correct |
12 ms |
12320 KB |
Output is correct |
24 |
Correct |
11 ms |
12320 KB |
Output is correct |
25 |
Correct |
11 ms |
12372 KB |
Output is correct |
26 |
Correct |
10 ms |
12244 KB |
Output is correct |
27 |
Correct |
9 ms |
12328 KB |
Output is correct |
28 |
Correct |
12 ms |
12272 KB |
Output is correct |
29 |
Correct |
13 ms |
12332 KB |
Output is correct |
30 |
Correct |
17 ms |
12324 KB |
Output is correct |
31 |
Correct |
15 ms |
12336 KB |
Output is correct |
32 |
Correct |
14 ms |
12244 KB |
Output is correct |
33 |
Correct |
12 ms |
12408 KB |
Output is correct |
34 |
Correct |
13 ms |
12456 KB |
Output is correct |
35 |
Correct |
11 ms |
12452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9940 KB |
Output is correct |
2 |
Correct |
17 ms |
12228 KB |
Output is correct |
3 |
Correct |
15 ms |
12316 KB |
Output is correct |
4 |
Correct |
17 ms |
12244 KB |
Output is correct |
5 |
Correct |
2424 ms |
150540 KB |
Output is correct |
6 |
Correct |
2029 ms |
123168 KB |
Output is correct |
7 |
Correct |
1724 ms |
121380 KB |
Output is correct |
8 |
Correct |
1529 ms |
119968 KB |
Output is correct |
9 |
Correct |
1646 ms |
123348 KB |
Output is correct |
10 |
Correct |
2769 ms |
161492 KB |
Output is correct |
11 |
Correct |
2726 ms |
161520 KB |
Output is correct |
12 |
Correct |
2771 ms |
161524 KB |
Output is correct |
13 |
Correct |
2926 ms |
161628 KB |
Output is correct |
14 |
Correct |
3103 ms |
161504 KB |
Output is correct |
15 |
Correct |
1552 ms |
173712 KB |
Output is correct |
16 |
Correct |
1512 ms |
173784 KB |
Output is correct |
17 |
Correct |
1441 ms |
173988 KB |
Output is correct |
18 |
Correct |
3222 ms |
161432 KB |
Output is correct |
19 |
Correct |
3267 ms |
161540 KB |
Output is correct |
20 |
Correct |
3058 ms |
161660 KB |
Output is correct |
21 |
Correct |
2647 ms |
160932 KB |
Output is correct |
22 |
Correct |
2585 ms |
161120 KB |
Output is correct |
23 |
Correct |
2700 ms |
161124 KB |
Output is correct |
24 |
Correct |
2871 ms |
161112 KB |
Output is correct |
25 |
Correct |
832 ms |
164540 KB |
Output is correct |
26 |
Correct |
890 ms |
164612 KB |
Output is correct |
27 |
Correct |
569 ms |
164456 KB |
Output is correct |
28 |
Correct |
386 ms |
161340 KB |
Output is correct |
29 |
Correct |
404 ms |
161272 KB |
Output is correct |
30 |
Correct |
2747 ms |
161564 KB |
Output is correct |
31 |
Correct |
2706 ms |
161532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9812 KB |
Output is correct |
2 |
Correct |
16 ms |
12500 KB |
Output is correct |
3 |
Correct |
13 ms |
12500 KB |
Output is correct |
4 |
Correct |
14 ms |
12452 KB |
Output is correct |
5 |
Correct |
817 ms |
134128 KB |
Output is correct |
6 |
Correct |
661 ms |
124304 KB |
Output is correct |
7 |
Correct |
1085 ms |
126440 KB |
Output is correct |
8 |
Correct |
1413 ms |
168580 KB |
Output is correct |
9 |
Correct |
1385 ms |
169336 KB |
Output is correct |
10 |
Correct |
1407 ms |
169976 KB |
Output is correct |
11 |
Correct |
470 ms |
172392 KB |
Output is correct |
12 |
Correct |
637 ms |
167584 KB |
Output is correct |
13 |
Correct |
458 ms |
172744 KB |
Output is correct |
14 |
Correct |
423 ms |
173536 KB |
Output is correct |
15 |
Correct |
357 ms |
172036 KB |
Output is correct |
16 |
Correct |
1035 ms |
168116 KB |
Output is correct |
17 |
Correct |
1038 ms |
169732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9856 KB |
Output is correct |
2 |
Correct |
5 ms |
9812 KB |
Output is correct |
3 |
Correct |
6 ms |
9812 KB |
Output is correct |
4 |
Correct |
6 ms |
9900 KB |
Output is correct |
5 |
Correct |
13 ms |
12076 KB |
Output is correct |
6 |
Correct |
14 ms |
12228 KB |
Output is correct |
7 |
Correct |
12 ms |
11556 KB |
Output is correct |
8 |
Correct |
16 ms |
12328 KB |
Output is correct |
9 |
Correct |
17 ms |
12244 KB |
Output is correct |
10 |
Correct |
15 ms |
12244 KB |
Output is correct |
11 |
Correct |
14 ms |
12332 KB |
Output is correct |
12 |
Correct |
14 ms |
12244 KB |
Output is correct |
13 |
Correct |
15 ms |
12452 KB |
Output is correct |
14 |
Correct |
15 ms |
12448 KB |
Output is correct |
15 |
Correct |
13 ms |
12360 KB |
Output is correct |
16 |
Correct |
16 ms |
12392 KB |
Output is correct |
17 |
Correct |
14 ms |
12328 KB |
Output is correct |
18 |
Correct |
16 ms |
12324 KB |
Output is correct |
19 |
Correct |
15 ms |
12244 KB |
Output is correct |
20 |
Correct |
13 ms |
12328 KB |
Output is correct |
21 |
Correct |
14 ms |
12320 KB |
Output is correct |
22 |
Correct |
14 ms |
12244 KB |
Output is correct |
23 |
Correct |
12 ms |
12320 KB |
Output is correct |
24 |
Correct |
11 ms |
12320 KB |
Output is correct |
25 |
Correct |
11 ms |
12372 KB |
Output is correct |
26 |
Correct |
10 ms |
12244 KB |
Output is correct |
27 |
Correct |
9 ms |
12328 KB |
Output is correct |
28 |
Correct |
12 ms |
12272 KB |
Output is correct |
29 |
Correct |
13 ms |
12332 KB |
Output is correct |
30 |
Correct |
17 ms |
12324 KB |
Output is correct |
31 |
Correct |
15 ms |
12336 KB |
Output is correct |
32 |
Correct |
14 ms |
12244 KB |
Output is correct |
33 |
Correct |
12 ms |
12408 KB |
Output is correct |
34 |
Correct |
13 ms |
12456 KB |
Output is correct |
35 |
Correct |
11 ms |
12452 KB |
Output is correct |
36 |
Correct |
5 ms |
9940 KB |
Output is correct |
37 |
Correct |
17 ms |
12228 KB |
Output is correct |
38 |
Correct |
15 ms |
12316 KB |
Output is correct |
39 |
Correct |
17 ms |
12244 KB |
Output is correct |
40 |
Correct |
2424 ms |
150540 KB |
Output is correct |
41 |
Correct |
2029 ms |
123168 KB |
Output is correct |
42 |
Correct |
1724 ms |
121380 KB |
Output is correct |
43 |
Correct |
1529 ms |
119968 KB |
Output is correct |
44 |
Correct |
1646 ms |
123348 KB |
Output is correct |
45 |
Correct |
2769 ms |
161492 KB |
Output is correct |
46 |
Correct |
2726 ms |
161520 KB |
Output is correct |
47 |
Correct |
2771 ms |
161524 KB |
Output is correct |
48 |
Correct |
2926 ms |
161628 KB |
Output is correct |
49 |
Correct |
3103 ms |
161504 KB |
Output is correct |
50 |
Correct |
1552 ms |
173712 KB |
Output is correct |
51 |
Correct |
1512 ms |
173784 KB |
Output is correct |
52 |
Correct |
1441 ms |
173988 KB |
Output is correct |
53 |
Correct |
3222 ms |
161432 KB |
Output is correct |
54 |
Correct |
3267 ms |
161540 KB |
Output is correct |
55 |
Correct |
3058 ms |
161660 KB |
Output is correct |
56 |
Correct |
2647 ms |
160932 KB |
Output is correct |
57 |
Correct |
2585 ms |
161120 KB |
Output is correct |
58 |
Correct |
2700 ms |
161124 KB |
Output is correct |
59 |
Correct |
2871 ms |
161112 KB |
Output is correct |
60 |
Correct |
832 ms |
164540 KB |
Output is correct |
61 |
Correct |
890 ms |
164612 KB |
Output is correct |
62 |
Correct |
569 ms |
164456 KB |
Output is correct |
63 |
Correct |
386 ms |
161340 KB |
Output is correct |
64 |
Correct |
404 ms |
161272 KB |
Output is correct |
65 |
Correct |
2747 ms |
161564 KB |
Output is correct |
66 |
Correct |
2706 ms |
161532 KB |
Output is correct |
67 |
Correct |
6 ms |
9812 KB |
Output is correct |
68 |
Correct |
16 ms |
12500 KB |
Output is correct |
69 |
Correct |
13 ms |
12500 KB |
Output is correct |
70 |
Correct |
14 ms |
12452 KB |
Output is correct |
71 |
Correct |
817 ms |
134128 KB |
Output is correct |
72 |
Correct |
661 ms |
124304 KB |
Output is correct |
73 |
Correct |
1085 ms |
126440 KB |
Output is correct |
74 |
Correct |
1413 ms |
168580 KB |
Output is correct |
75 |
Correct |
1385 ms |
169336 KB |
Output is correct |
76 |
Correct |
1407 ms |
169976 KB |
Output is correct |
77 |
Correct |
470 ms |
172392 KB |
Output is correct |
78 |
Correct |
637 ms |
167584 KB |
Output is correct |
79 |
Correct |
458 ms |
172744 KB |
Output is correct |
80 |
Correct |
423 ms |
173536 KB |
Output is correct |
81 |
Correct |
357 ms |
172036 KB |
Output is correct |
82 |
Correct |
1035 ms |
168116 KB |
Output is correct |
83 |
Correct |
1038 ms |
169732 KB |
Output is correct |
84 |
Correct |
2371 ms |
141244 KB |
Output is correct |
85 |
Correct |
1917 ms |
113900 KB |
Output is correct |
86 |
Correct |
1297 ms |
93852 KB |
Output is correct |
87 |
Correct |
2970 ms |
161452 KB |
Output is correct |
88 |
Correct |
3102 ms |
160828 KB |
Output is correct |
89 |
Correct |
2990 ms |
161464 KB |
Output is correct |
90 |
Correct |
2973 ms |
161464 KB |
Output is correct |
91 |
Correct |
3000 ms |
161456 KB |
Output is correct |
92 |
Correct |
1530 ms |
168976 KB |
Output is correct |
93 |
Correct |
1460 ms |
168184 KB |
Output is correct |
94 |
Correct |
3066 ms |
161608 KB |
Output is correct |
95 |
Correct |
3002 ms |
161712 KB |
Output is correct |
96 |
Correct |
3083 ms |
161480 KB |
Output is correct |
97 |
Correct |
3070 ms |
161564 KB |
Output is correct |
98 |
Correct |
2483 ms |
161108 KB |
Output is correct |
99 |
Correct |
2391 ms |
160992 KB |
Output is correct |
100 |
Correct |
2451 ms |
160828 KB |
Output is correct |
101 |
Correct |
2446 ms |
161092 KB |
Output is correct |
102 |
Correct |
474 ms |
164448 KB |
Output is correct |
103 |
Correct |
687 ms |
164556 KB |
Output is correct |
104 |
Correct |
775 ms |
164532 KB |
Output is correct |
105 |
Correct |
351 ms |
161628 KB |
Output is correct |
106 |
Correct |
341 ms |
161016 KB |
Output is correct |
107 |
Correct |
2379 ms |
161428 KB |
Output is correct |
108 |
Correct |
2491 ms |
161384 KB |
Output is correct |