#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct fenwick_tree {
long long fenw[N];
fenwick_tree() {
memset(fenw, 0, sizeof(fenw));
}
void reset() {
memset(fenw, 0, sizeof(fenw));
}
void upd(int idx, int val) {
for (; idx < N; idx |= (idx + 1)) {
fenw[idx] += val;
}
}
long long get(int idx) {
long long res = 0;
for (; idx >= 0; idx &= (idx + 1), --idx) {
res += fenw[idx];
}
return res;
}
long long get(int l, int r) {
return get(r) - get(l - 1);
}
};
int n, m, q;
int a[N], b[N];
int p[N], c[N];
int ord[N];
int s[N], t[N], x[N];
long long y[N];
int l[N], r[N], ans[N];
vector<int> cand[N];
vector<pair<int, int>> g[N];
int dep[N], sz[N], son[N], fa[N], head[N], pos[N];
int hld_timer = 0;
fenwick_tree gold, silver;
void dfs(int u, int p, int d, int pid) {
sz[u] = 1;
fa[u] = p;
dep[u] = d;
int mx = 0;
for (pair<int, int> &e : g[u]) {
int v, id;
tie(v, id) = e;
if (id == pid) {
continue;
}
dfs(v, u, d + 1, id);
sz[u] += sz[v];
if (sz[v] > mx) {
mx = sz[v];
son[u] = v;
}
}
}
void decompose(int u, int p, int h) {
head[u] = h;
pos[u] = ++hld_timer;
if (son[u] != 0) {
decompose(son[u], u, h);
}
for (pair<int, int> &e : g[u]) {
int v, id;
tie(v, id) = e;
if (v == p || v == son[u]) {
continue;
}
decompose(v, u, v);
}
}
void silver_upd(int i, int w) {
int u = dep[a[i]] > dep[b[i]] ? a[i] : b[i];
silver.upd(pos[u], w);
}
void gold_upd(int i, int w) {
int u = dep[a[i]] > dep[b[i]] ? a[i] : b[i];
gold.upd(pos[u], w);
}
int gold_que(int u, int v) {
int sum = 0;
while (head[u] != head[v]) {
if (dep[head[u]] > dep[head[v]]) {
swap(u, v);
}
sum += gold.get(pos[head[v]], pos[v]);
v = fa[head[v]];
}
if (dep[u] > dep[v]) {
swap(u, v);
}
if (pos[u] < pos[v]) {
sum += gold.get(pos[u] + 1, pos[v]);
}
return sum;
}
long long silver_que(int u, int v) {
long long sum = 0;
while (head[u] != head[v]) {
if (dep[head[u]] > dep[head[v]]) {
swap(u, v);
}
sum += silver.get(pos[head[v]], pos[v]);
v = fa[head[v]];
}
if (dep[u] > dep[v]) {
swap(u, v);
}
if (pos[u] < pos[v]) {
sum += silver.get(pos[u] + 1, pos[v]);
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; i++) {
cin >> a[i] >> b[i];
g[a[i]].emplace_back(b[i], i);
g[b[i]].emplace_back(a[i], i);
}
dfs(1, 1, 0, 0);
decompose(1, 1, 1);
for (int i = 1; i <= m; i++) {
cin >> p[i] >> c[i];
}
iota(ord + 1, ord + m + 1, 1);
sort(ord + 1, ord + m + 1, [](const int &u, const int &v) -> bool {
return c[u] < c[v];
});
for (int i = 1; i <= q; i++) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
l[i] = 1;
r[i] = m + 1;
ans[i] = -1;
}
for (int ite = 1; ite <= 20; ite++) {
silver.reset();
gold.reset();
for (int i = 1; i <= m; i++) {
silver_upd(p[i], c[i]);
}
for (int i = 1; i <= m + 1; i++) {
cand[i].clear();
}
for (int i = 1; i <= q; i++) {
if (l[i] > r[i]) {
continue;
}
cand[l[i] + r[i] >> 1].emplace_back(i);
}
for (int i = m + 1; i >= 1; i--) {
if (i != m + 1) {
silver_upd(p[ord[i]], -c[ord[i]]);
gold_upd(p[ord[i]], +1);
}
for (int &idx : cand[i]) {
if (silver_que(s[idx], t[idx]) <= y[idx]) {
if (gold_que(s[idx], t[idx]) <= x[idx]) {
ans[idx] = x[idx] - gold_que(s[idx], t[idx]);
}
l[idx] = i + 1;
} else {
r[idx] = i - 1;
}
}
}
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:169:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
169 | cand[l[i] + r[i] >> 1].emplace_back(i);
| ~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6612 KB |
Output is correct |
2 |
Correct |
3 ms |
6600 KB |
Output is correct |
3 |
Correct |
4 ms |
6612 KB |
Output is correct |
4 |
Correct |
4 ms |
6612 KB |
Output is correct |
5 |
Correct |
11 ms |
6992 KB |
Output is correct |
6 |
Correct |
14 ms |
7012 KB |
Output is correct |
7 |
Correct |
12 ms |
6996 KB |
Output is correct |
8 |
Correct |
13 ms |
7124 KB |
Output is correct |
9 |
Correct |
13 ms |
7120 KB |
Output is correct |
10 |
Correct |
14 ms |
7124 KB |
Output is correct |
11 |
Correct |
19 ms |
7136 KB |
Output is correct |
12 |
Correct |
15 ms |
7056 KB |
Output is correct |
13 |
Correct |
10 ms |
7268 KB |
Output is correct |
14 |
Correct |
10 ms |
7124 KB |
Output is correct |
15 |
Correct |
14 ms |
7172 KB |
Output is correct |
16 |
Correct |
11 ms |
7144 KB |
Output is correct |
17 |
Correct |
12 ms |
7124 KB |
Output is correct |
18 |
Correct |
12 ms |
7124 KB |
Output is correct |
19 |
Correct |
12 ms |
7120 KB |
Output is correct |
20 |
Correct |
12 ms |
7120 KB |
Output is correct |
21 |
Correct |
12 ms |
7252 KB |
Output is correct |
22 |
Correct |
11 ms |
7124 KB |
Output is correct |
23 |
Correct |
12 ms |
7124 KB |
Output is correct |
24 |
Correct |
12 ms |
7128 KB |
Output is correct |
25 |
Correct |
12 ms |
7088 KB |
Output is correct |
26 |
Correct |
10 ms |
7004 KB |
Output is correct |
27 |
Correct |
14 ms |
7100 KB |
Output is correct |
28 |
Correct |
11 ms |
7000 KB |
Output is correct |
29 |
Correct |
10 ms |
6996 KB |
Output is correct |
30 |
Correct |
13 ms |
7044 KB |
Output is correct |
31 |
Correct |
14 ms |
7036 KB |
Output is correct |
32 |
Correct |
18 ms |
7124 KB |
Output is correct |
33 |
Correct |
10 ms |
7196 KB |
Output is correct |
34 |
Correct |
10 ms |
7172 KB |
Output is correct |
35 |
Correct |
10 ms |
7252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6612 KB |
Output is correct |
2 |
Correct |
14 ms |
7120 KB |
Output is correct |
3 |
Correct |
14 ms |
7124 KB |
Output is correct |
4 |
Correct |
14 ms |
7120 KB |
Output is correct |
5 |
Correct |
1012 ms |
26924 KB |
Output is correct |
6 |
Correct |
1307 ms |
29728 KB |
Output is correct |
7 |
Correct |
1207 ms |
29056 KB |
Output is correct |
8 |
Correct |
898 ms |
25548 KB |
Output is correct |
9 |
Correct |
884 ms |
25048 KB |
Output is correct |
10 |
Correct |
1457 ms |
32992 KB |
Output is correct |
11 |
Correct |
1491 ms |
32952 KB |
Output is correct |
12 |
Correct |
1388 ms |
32996 KB |
Output is correct |
13 |
Correct |
1412 ms |
32836 KB |
Output is correct |
14 |
Correct |
1445 ms |
33124 KB |
Output is correct |
15 |
Correct |
607 ms |
40508 KB |
Output is correct |
16 |
Correct |
653 ms |
40972 KB |
Output is correct |
17 |
Correct |
637 ms |
40060 KB |
Output is correct |
18 |
Correct |
1077 ms |
33008 KB |
Output is correct |
19 |
Correct |
1115 ms |
32960 KB |
Output is correct |
20 |
Correct |
1072 ms |
33004 KB |
Output is correct |
21 |
Correct |
652 ms |
32652 KB |
Output is correct |
22 |
Correct |
691 ms |
32852 KB |
Output is correct |
23 |
Correct |
667 ms |
33272 KB |
Output is correct |
24 |
Correct |
667 ms |
33164 KB |
Output is correct |
25 |
Correct |
1103 ms |
33632 KB |
Output is correct |
26 |
Correct |
1177 ms |
33172 KB |
Output is correct |
27 |
Correct |
1115 ms |
33684 KB |
Output is correct |
28 |
Correct |
657 ms |
32040 KB |
Output is correct |
29 |
Correct |
582 ms |
30892 KB |
Output is correct |
30 |
Correct |
862 ms |
31348 KB |
Output is correct |
31 |
Correct |
770 ms |
31368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6612 KB |
Output is correct |
2 |
Correct |
10 ms |
7252 KB |
Output is correct |
3 |
Correct |
10 ms |
7252 KB |
Output is correct |
4 |
Correct |
10 ms |
7252 KB |
Output is correct |
5 |
Correct |
332 ms |
33648 KB |
Output is correct |
6 |
Correct |
309 ms |
33076 KB |
Output is correct |
7 |
Correct |
471 ms |
31888 KB |
Output is correct |
8 |
Correct |
534 ms |
41272 KB |
Output is correct |
9 |
Correct |
569 ms |
41140 KB |
Output is correct |
10 |
Correct |
545 ms |
41156 KB |
Output is correct |
11 |
Correct |
440 ms |
41236 KB |
Output is correct |
12 |
Correct |
420 ms |
41352 KB |
Output is correct |
13 |
Correct |
472 ms |
41156 KB |
Output is correct |
14 |
Correct |
490 ms |
40524 KB |
Output is correct |
15 |
Correct |
421 ms |
40192 KB |
Output is correct |
16 |
Correct |
443 ms |
40800 KB |
Output is correct |
17 |
Correct |
502 ms |
40732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6612 KB |
Output is correct |
2 |
Correct |
3 ms |
6600 KB |
Output is correct |
3 |
Correct |
4 ms |
6612 KB |
Output is correct |
4 |
Correct |
4 ms |
6612 KB |
Output is correct |
5 |
Correct |
11 ms |
6992 KB |
Output is correct |
6 |
Correct |
14 ms |
7012 KB |
Output is correct |
7 |
Correct |
12 ms |
6996 KB |
Output is correct |
8 |
Correct |
13 ms |
7124 KB |
Output is correct |
9 |
Correct |
13 ms |
7120 KB |
Output is correct |
10 |
Correct |
14 ms |
7124 KB |
Output is correct |
11 |
Correct |
19 ms |
7136 KB |
Output is correct |
12 |
Correct |
15 ms |
7056 KB |
Output is correct |
13 |
Correct |
10 ms |
7268 KB |
Output is correct |
14 |
Correct |
10 ms |
7124 KB |
Output is correct |
15 |
Correct |
14 ms |
7172 KB |
Output is correct |
16 |
Correct |
11 ms |
7144 KB |
Output is correct |
17 |
Correct |
12 ms |
7124 KB |
Output is correct |
18 |
Correct |
12 ms |
7124 KB |
Output is correct |
19 |
Correct |
12 ms |
7120 KB |
Output is correct |
20 |
Correct |
12 ms |
7120 KB |
Output is correct |
21 |
Correct |
12 ms |
7252 KB |
Output is correct |
22 |
Correct |
11 ms |
7124 KB |
Output is correct |
23 |
Correct |
12 ms |
7124 KB |
Output is correct |
24 |
Correct |
12 ms |
7128 KB |
Output is correct |
25 |
Correct |
12 ms |
7088 KB |
Output is correct |
26 |
Correct |
10 ms |
7004 KB |
Output is correct |
27 |
Correct |
14 ms |
7100 KB |
Output is correct |
28 |
Correct |
11 ms |
7000 KB |
Output is correct |
29 |
Correct |
10 ms |
6996 KB |
Output is correct |
30 |
Correct |
13 ms |
7044 KB |
Output is correct |
31 |
Correct |
14 ms |
7036 KB |
Output is correct |
32 |
Correct |
18 ms |
7124 KB |
Output is correct |
33 |
Correct |
10 ms |
7196 KB |
Output is correct |
34 |
Correct |
10 ms |
7172 KB |
Output is correct |
35 |
Correct |
10 ms |
7252 KB |
Output is correct |
36 |
Correct |
3 ms |
6612 KB |
Output is correct |
37 |
Correct |
14 ms |
7120 KB |
Output is correct |
38 |
Correct |
14 ms |
7124 KB |
Output is correct |
39 |
Correct |
14 ms |
7120 KB |
Output is correct |
40 |
Correct |
1012 ms |
26924 KB |
Output is correct |
41 |
Correct |
1307 ms |
29728 KB |
Output is correct |
42 |
Correct |
1207 ms |
29056 KB |
Output is correct |
43 |
Correct |
898 ms |
25548 KB |
Output is correct |
44 |
Correct |
884 ms |
25048 KB |
Output is correct |
45 |
Correct |
1457 ms |
32992 KB |
Output is correct |
46 |
Correct |
1491 ms |
32952 KB |
Output is correct |
47 |
Correct |
1388 ms |
32996 KB |
Output is correct |
48 |
Correct |
1412 ms |
32836 KB |
Output is correct |
49 |
Correct |
1445 ms |
33124 KB |
Output is correct |
50 |
Correct |
607 ms |
40508 KB |
Output is correct |
51 |
Correct |
653 ms |
40972 KB |
Output is correct |
52 |
Correct |
637 ms |
40060 KB |
Output is correct |
53 |
Correct |
1077 ms |
33008 KB |
Output is correct |
54 |
Correct |
1115 ms |
32960 KB |
Output is correct |
55 |
Correct |
1072 ms |
33004 KB |
Output is correct |
56 |
Correct |
652 ms |
32652 KB |
Output is correct |
57 |
Correct |
691 ms |
32852 KB |
Output is correct |
58 |
Correct |
667 ms |
33272 KB |
Output is correct |
59 |
Correct |
667 ms |
33164 KB |
Output is correct |
60 |
Correct |
1103 ms |
33632 KB |
Output is correct |
61 |
Correct |
1177 ms |
33172 KB |
Output is correct |
62 |
Correct |
1115 ms |
33684 KB |
Output is correct |
63 |
Correct |
657 ms |
32040 KB |
Output is correct |
64 |
Correct |
582 ms |
30892 KB |
Output is correct |
65 |
Correct |
862 ms |
31348 KB |
Output is correct |
66 |
Correct |
770 ms |
31368 KB |
Output is correct |
67 |
Correct |
5 ms |
6612 KB |
Output is correct |
68 |
Correct |
10 ms |
7252 KB |
Output is correct |
69 |
Correct |
10 ms |
7252 KB |
Output is correct |
70 |
Correct |
10 ms |
7252 KB |
Output is correct |
71 |
Correct |
332 ms |
33648 KB |
Output is correct |
72 |
Correct |
309 ms |
33076 KB |
Output is correct |
73 |
Correct |
471 ms |
31888 KB |
Output is correct |
74 |
Correct |
534 ms |
41272 KB |
Output is correct |
75 |
Correct |
569 ms |
41140 KB |
Output is correct |
76 |
Correct |
545 ms |
41156 KB |
Output is correct |
77 |
Correct |
440 ms |
41236 KB |
Output is correct |
78 |
Correct |
420 ms |
41352 KB |
Output is correct |
79 |
Correct |
472 ms |
41156 KB |
Output is correct |
80 |
Correct |
490 ms |
40524 KB |
Output is correct |
81 |
Correct |
421 ms |
40192 KB |
Output is correct |
82 |
Correct |
443 ms |
40800 KB |
Output is correct |
83 |
Correct |
502 ms |
40732 KB |
Output is correct |
84 |
Correct |
1039 ms |
26176 KB |
Output is correct |
85 |
Correct |
1106 ms |
25372 KB |
Output is correct |
86 |
Correct |
935 ms |
24488 KB |
Output is correct |
87 |
Correct |
1391 ms |
33084 KB |
Output is correct |
88 |
Correct |
1414 ms |
32932 KB |
Output is correct |
89 |
Correct |
1361 ms |
32972 KB |
Output is correct |
90 |
Correct |
1402 ms |
33152 KB |
Output is correct |
91 |
Correct |
1359 ms |
32996 KB |
Output is correct |
92 |
Correct |
634 ms |
38132 KB |
Output is correct |
93 |
Correct |
611 ms |
39824 KB |
Output is correct |
94 |
Correct |
1026 ms |
33004 KB |
Output is correct |
95 |
Correct |
1069 ms |
33024 KB |
Output is correct |
96 |
Correct |
1029 ms |
32972 KB |
Output is correct |
97 |
Correct |
1069 ms |
32968 KB |
Output is correct |
98 |
Correct |
632 ms |
32836 KB |
Output is correct |
99 |
Correct |
659 ms |
32524 KB |
Output is correct |
100 |
Correct |
734 ms |
33192 KB |
Output is correct |
101 |
Correct |
678 ms |
33432 KB |
Output is correct |
102 |
Correct |
1108 ms |
33604 KB |
Output is correct |
103 |
Correct |
1000 ms |
33648 KB |
Output is correct |
104 |
Correct |
1002 ms |
33628 KB |
Output is correct |
105 |
Correct |
707 ms |
30812 KB |
Output is correct |
106 |
Correct |
631 ms |
31740 KB |
Output is correct |
107 |
Correct |
741 ms |
30772 KB |
Output is correct |
108 |
Correct |
703 ms |
30980 KB |
Output is correct |