#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int M = (1 << 18);
ll t[2 * M];
void update(int ql, int qr, ll add) {
for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
if(ql & 1) t[ql++] += add;
if(qr & 1) t[--qr] += add;
}
}
ll get(int pos) {
ll res = 0;
for(pos += M; pos; pos >>= 1)
res += t[pos];
return res;
}
struct edge {
int u, v, i;
};
struct query {
ll i, s, t, x, y;
};
int n, m, q;
vector<edge> edges;
vector<pair<int, int>> checkpoints;
vector<query> queries;
vector<int> g[N];
int tin[N], tout[N], depth[N], anc[N][18], T, cnt[N], fla[N];
void precalc(int s, int p) {
tin[s] = T++;
anc[s][0] = p;
for(int i = 1; i < 18; i++)
anc[s][i] = anc[anc[s][i - 1]][i - 1];
for(int to : g[s]) {
if(to == p) continue;
depth[to] = depth[s] + 1;
precalc(to, s);
}
tout[s] = T++;
}
void dfs(int s, int p) {
cnt[s] = cnt[p] + fla[s];
for(int to : g[s]) {
if(to == p) continue;
dfs(to, s);
}
}
bool up(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if(up(u, v)) return u;
if(up(v, u)) return v;
for(int i = 17; i >= 0; i--) {
if(!up(anc[u][i], v))
u = anc[u][i];
}
return anc[u][0];
}
int count(int a, int b) {
return cnt[a] + cnt[b] - 2 * cnt[lca(a, b)];
}
ll func(int a, int b) {
return get(tin[a]) + get(tin[b]) - 2 * get(tin[lca(a, b)]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
edges.resize(n - 1);
checkpoints.resize(m + 1);
queries.resize(q);
vector<int> tl(q), tr(q);
for(int i = 0; i < n - 1; i++) {
cin >> edges[i].u >> edges[i].v;
edges[i].i = i;
g[edges[i].u].push_back(edges[i].v);
g[edges[i].v].push_back(edges[i].u);
}
precalc(1, 1);
for(int i = 1; i <= m; i++) {
cin >> checkpoints[i].first >> checkpoints[i].second;
auto [u, v, ix] = edges[checkpoints[i].first - 1];
if(depth[u] > depth[v]) swap(u, v);
checkpoints[i].first = v;
fla[v]++;
}
sort(checkpoints.begin(), checkpoints.end(), [](pair<int, int> r1, pair<int, int> r2) {
return (r1.second < r2.second);
});
// -- INPUT END --
dfs(1, 1);
for(int i = 0; i < q; i++) {
cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;
queries[i].i = i;
tl[i] = 0, tr[i] = m + 1;
}
for(int iter = 0; iter < 18; iter++) {
vector<int> oper[m + 1];
for(int i = 0; i < q; i++) {
oper[(tl[i] + tr[i]) / 2].push_back(i);
}
for(int i = 0; i <= m; i++) {
if(i) {auto [v, c] = checkpoints[i]; update(tin[v], tout[v], c); }
for(int p : oper[i]) {
if(func(queries[p].s, queries[p].t) <= queries[p].y)
tl[p] = i;
else
tr[p] = i;
}
}
// return 0;
for(int i = 1; i <= m; i++) {
auto [v, c] = checkpoints[i];
update(tin[v], tout[v], -c);
}
}
vector<int> oper[m + 1];
for(int i = 0; i < q; i++) {
oper[tl[i]].push_back(i);
}
int p = 0;
vector<int> answers(q);
for(int i = 0; i <= m; i++) {
if(i) {auto [v, c] = checkpoints[i]; update(tin[v], tout[v], 1);}
for(int p : oper[i]) {
int ans = queries[p].x - count(queries[p].s, queries[p].t) + func(queries[p].s, queries[p].t);
answers[p] = (ans < 0 ? -1 : ans);
}
}
for(int c : answers)
cout << c << '\n';
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:136:9: warning: unused variable 'p' [-Wunused-variable]
136 | int p = 0;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
8 ms |
3156 KB |
Output is correct |
6 |
Correct |
11 ms |
3284 KB |
Output is correct |
7 |
Correct |
10 ms |
3156 KB |
Output is correct |
8 |
Correct |
12 ms |
3280 KB |
Output is correct |
9 |
Correct |
14 ms |
3284 KB |
Output is correct |
10 |
Correct |
12 ms |
3284 KB |
Output is correct |
11 |
Correct |
12 ms |
3264 KB |
Output is correct |
12 |
Correct |
12 ms |
3284 KB |
Output is correct |
13 |
Correct |
11 ms |
3284 KB |
Output is correct |
14 |
Correct |
13 ms |
3300 KB |
Output is correct |
15 |
Correct |
14 ms |
3284 KB |
Output is correct |
16 |
Correct |
15 ms |
3284 KB |
Output is correct |
17 |
Correct |
14 ms |
3284 KB |
Output is correct |
18 |
Correct |
14 ms |
3272 KB |
Output is correct |
19 |
Correct |
11 ms |
3272 KB |
Output is correct |
20 |
Correct |
11 ms |
3208 KB |
Output is correct |
21 |
Correct |
11 ms |
3156 KB |
Output is correct |
22 |
Correct |
11 ms |
3292 KB |
Output is correct |
23 |
Correct |
11 ms |
3280 KB |
Output is correct |
24 |
Correct |
13 ms |
3200 KB |
Output is correct |
25 |
Correct |
11 ms |
3264 KB |
Output is correct |
26 |
Correct |
11 ms |
3156 KB |
Output is correct |
27 |
Correct |
10 ms |
3260 KB |
Output is correct |
28 |
Correct |
11 ms |
3264 KB |
Output is correct |
29 |
Correct |
10 ms |
3156 KB |
Output is correct |
30 |
Correct |
12 ms |
3276 KB |
Output is correct |
31 |
Correct |
12 ms |
3284 KB |
Output is correct |
32 |
Correct |
12 ms |
3268 KB |
Output is correct |
33 |
Correct |
10 ms |
3284 KB |
Output is correct |
34 |
Correct |
10 ms |
3332 KB |
Output is correct |
35 |
Correct |
12 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
12 ms |
3264 KB |
Output is correct |
3 |
Correct |
12 ms |
3284 KB |
Output is correct |
4 |
Correct |
12 ms |
3260 KB |
Output is correct |
5 |
Correct |
617 ms |
26092 KB |
Output is correct |
6 |
Correct |
767 ms |
27800 KB |
Output is correct |
7 |
Correct |
767 ms |
29000 KB |
Output is correct |
8 |
Correct |
687 ms |
27328 KB |
Output is correct |
9 |
Correct |
627 ms |
27016 KB |
Output is correct |
10 |
Correct |
1132 ms |
34048 KB |
Output is correct |
11 |
Correct |
1041 ms |
34072 KB |
Output is correct |
12 |
Correct |
991 ms |
33964 KB |
Output is correct |
13 |
Correct |
973 ms |
33924 KB |
Output is correct |
14 |
Correct |
1073 ms |
34028 KB |
Output is correct |
15 |
Correct |
984 ms |
39000 KB |
Output is correct |
16 |
Correct |
823 ms |
39396 KB |
Output is correct |
17 |
Correct |
1051 ms |
38644 KB |
Output is correct |
18 |
Correct |
1439 ms |
34352 KB |
Output is correct |
19 |
Correct |
1449 ms |
34404 KB |
Output is correct |
20 |
Correct |
1494 ms |
34488 KB |
Output is correct |
21 |
Correct |
733 ms |
31960 KB |
Output is correct |
22 |
Correct |
739 ms |
32104 KB |
Output is correct |
23 |
Correct |
755 ms |
33744 KB |
Output is correct |
24 |
Correct |
831 ms |
33772 KB |
Output is correct |
25 |
Correct |
766 ms |
34732 KB |
Output is correct |
26 |
Correct |
788 ms |
34768 KB |
Output is correct |
27 |
Correct |
841 ms |
34804 KB |
Output is correct |
28 |
Correct |
552 ms |
33556 KB |
Output is correct |
29 |
Correct |
544 ms |
33412 KB |
Output is correct |
30 |
Correct |
586 ms |
33580 KB |
Output is correct |
31 |
Correct |
576 ms |
33628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
10 ms |
3360 KB |
Output is correct |
3 |
Correct |
10 ms |
3284 KB |
Output is correct |
4 |
Correct |
12 ms |
3284 KB |
Output is correct |
5 |
Correct |
461 ms |
29720 KB |
Output is correct |
6 |
Correct |
427 ms |
33316 KB |
Output is correct |
7 |
Correct |
577 ms |
27364 KB |
Output is correct |
8 |
Correct |
786 ms |
39404 KB |
Output is correct |
9 |
Correct |
772 ms |
39436 KB |
Output is correct |
10 |
Correct |
724 ms |
39564 KB |
Output is correct |
11 |
Correct |
612 ms |
39308 KB |
Output is correct |
12 |
Correct |
623 ms |
39444 KB |
Output is correct |
13 |
Correct |
548 ms |
39308 KB |
Output is correct |
14 |
Correct |
669 ms |
38500 KB |
Output is correct |
15 |
Correct |
657 ms |
38204 KB |
Output is correct |
16 |
Correct |
729 ms |
38776 KB |
Output is correct |
17 |
Correct |
675 ms |
38724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
8 ms |
3156 KB |
Output is correct |
6 |
Correct |
11 ms |
3284 KB |
Output is correct |
7 |
Correct |
10 ms |
3156 KB |
Output is correct |
8 |
Correct |
12 ms |
3280 KB |
Output is correct |
9 |
Correct |
14 ms |
3284 KB |
Output is correct |
10 |
Correct |
12 ms |
3284 KB |
Output is correct |
11 |
Correct |
12 ms |
3264 KB |
Output is correct |
12 |
Correct |
12 ms |
3284 KB |
Output is correct |
13 |
Correct |
11 ms |
3284 KB |
Output is correct |
14 |
Correct |
13 ms |
3300 KB |
Output is correct |
15 |
Correct |
14 ms |
3284 KB |
Output is correct |
16 |
Correct |
15 ms |
3284 KB |
Output is correct |
17 |
Correct |
14 ms |
3284 KB |
Output is correct |
18 |
Correct |
14 ms |
3272 KB |
Output is correct |
19 |
Correct |
11 ms |
3272 KB |
Output is correct |
20 |
Correct |
11 ms |
3208 KB |
Output is correct |
21 |
Correct |
11 ms |
3156 KB |
Output is correct |
22 |
Correct |
11 ms |
3292 KB |
Output is correct |
23 |
Correct |
11 ms |
3280 KB |
Output is correct |
24 |
Correct |
13 ms |
3200 KB |
Output is correct |
25 |
Correct |
11 ms |
3264 KB |
Output is correct |
26 |
Correct |
11 ms |
3156 KB |
Output is correct |
27 |
Correct |
10 ms |
3260 KB |
Output is correct |
28 |
Correct |
11 ms |
3264 KB |
Output is correct |
29 |
Correct |
10 ms |
3156 KB |
Output is correct |
30 |
Correct |
12 ms |
3276 KB |
Output is correct |
31 |
Correct |
12 ms |
3284 KB |
Output is correct |
32 |
Correct |
12 ms |
3268 KB |
Output is correct |
33 |
Correct |
10 ms |
3284 KB |
Output is correct |
34 |
Correct |
10 ms |
3332 KB |
Output is correct |
35 |
Correct |
12 ms |
3412 KB |
Output is correct |
36 |
Correct |
1 ms |
2644 KB |
Output is correct |
37 |
Correct |
12 ms |
3264 KB |
Output is correct |
38 |
Correct |
12 ms |
3284 KB |
Output is correct |
39 |
Correct |
12 ms |
3260 KB |
Output is correct |
40 |
Correct |
617 ms |
26092 KB |
Output is correct |
41 |
Correct |
767 ms |
27800 KB |
Output is correct |
42 |
Correct |
767 ms |
29000 KB |
Output is correct |
43 |
Correct |
687 ms |
27328 KB |
Output is correct |
44 |
Correct |
627 ms |
27016 KB |
Output is correct |
45 |
Correct |
1132 ms |
34048 KB |
Output is correct |
46 |
Correct |
1041 ms |
34072 KB |
Output is correct |
47 |
Correct |
991 ms |
33964 KB |
Output is correct |
48 |
Correct |
973 ms |
33924 KB |
Output is correct |
49 |
Correct |
1073 ms |
34028 KB |
Output is correct |
50 |
Correct |
984 ms |
39000 KB |
Output is correct |
51 |
Correct |
823 ms |
39396 KB |
Output is correct |
52 |
Correct |
1051 ms |
38644 KB |
Output is correct |
53 |
Correct |
1439 ms |
34352 KB |
Output is correct |
54 |
Correct |
1449 ms |
34404 KB |
Output is correct |
55 |
Correct |
1494 ms |
34488 KB |
Output is correct |
56 |
Correct |
733 ms |
31960 KB |
Output is correct |
57 |
Correct |
739 ms |
32104 KB |
Output is correct |
58 |
Correct |
755 ms |
33744 KB |
Output is correct |
59 |
Correct |
831 ms |
33772 KB |
Output is correct |
60 |
Correct |
766 ms |
34732 KB |
Output is correct |
61 |
Correct |
788 ms |
34768 KB |
Output is correct |
62 |
Correct |
841 ms |
34804 KB |
Output is correct |
63 |
Correct |
552 ms |
33556 KB |
Output is correct |
64 |
Correct |
544 ms |
33412 KB |
Output is correct |
65 |
Correct |
586 ms |
33580 KB |
Output is correct |
66 |
Correct |
576 ms |
33628 KB |
Output is correct |
67 |
Correct |
1 ms |
2644 KB |
Output is correct |
68 |
Correct |
10 ms |
3360 KB |
Output is correct |
69 |
Correct |
10 ms |
3284 KB |
Output is correct |
70 |
Correct |
12 ms |
3284 KB |
Output is correct |
71 |
Correct |
461 ms |
29720 KB |
Output is correct |
72 |
Correct |
427 ms |
33316 KB |
Output is correct |
73 |
Correct |
577 ms |
27364 KB |
Output is correct |
74 |
Correct |
786 ms |
39404 KB |
Output is correct |
75 |
Correct |
772 ms |
39436 KB |
Output is correct |
76 |
Correct |
724 ms |
39564 KB |
Output is correct |
77 |
Correct |
612 ms |
39308 KB |
Output is correct |
78 |
Correct |
623 ms |
39444 KB |
Output is correct |
79 |
Correct |
548 ms |
39308 KB |
Output is correct |
80 |
Correct |
669 ms |
38500 KB |
Output is correct |
81 |
Correct |
657 ms |
38204 KB |
Output is correct |
82 |
Correct |
729 ms |
38776 KB |
Output is correct |
83 |
Correct |
675 ms |
38724 KB |
Output is correct |
84 |
Correct |
575 ms |
27968 KB |
Output is correct |
85 |
Correct |
614 ms |
23620 KB |
Output is correct |
86 |
Correct |
554 ms |
22380 KB |
Output is correct |
87 |
Correct |
939 ms |
34004 KB |
Output is correct |
88 |
Correct |
977 ms |
33984 KB |
Output is correct |
89 |
Correct |
984 ms |
34016 KB |
Output is correct |
90 |
Correct |
977 ms |
33992 KB |
Output is correct |
91 |
Correct |
1025 ms |
33968 KB |
Output is correct |
92 |
Correct |
1277 ms |
37104 KB |
Output is correct |
93 |
Correct |
1091 ms |
38456 KB |
Output is correct |
94 |
Correct |
1405 ms |
34396 KB |
Output is correct |
95 |
Correct |
1460 ms |
34408 KB |
Output is correct |
96 |
Correct |
1424 ms |
34484 KB |
Output is correct |
97 |
Correct |
1437 ms |
34508 KB |
Output is correct |
98 |
Correct |
740 ms |
32108 KB |
Output is correct |
99 |
Correct |
754 ms |
32076 KB |
Output is correct |
100 |
Correct |
849 ms |
33704 KB |
Output is correct |
101 |
Correct |
808 ms |
33864 KB |
Output is correct |
102 |
Correct |
847 ms |
34720 KB |
Output is correct |
103 |
Correct |
833 ms |
34752 KB |
Output is correct |
104 |
Correct |
958 ms |
34804 KB |
Output is correct |
105 |
Correct |
551 ms |
33416 KB |
Output is correct |
106 |
Correct |
535 ms |
33576 KB |
Output is correct |
107 |
Correct |
569 ms |
33464 KB |
Output is correct |
108 |
Correct |
633 ms |
33452 KB |
Output is correct |