#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 20 * N;
const int inf = 1e9;
vector<pair<int, int>> g[N];
int par[N][17], in[N], out[N], tsz, psz;
void Dfs(int s, int e) {
par[s][0] = e;
for (int i = 1; i < 17; i++) par[s][i] = par[par[s][i - 1]][i - 1];
in[s] = ++tsz;
for (auto u : g[s]) {
if (u.first != e) {
Dfs(u.first, s);
}
}
out[s] = tsz;
}
bool Ancestor(int u, int v) {
return in[u] <= in[v] && out[v] <= out[u];
}
int Lca(int u, int v) {
if (Ancestor(u, v)) return u;
if (Ancestor(v, u)) return v;
for (int i = 16; i >= 0; i--) {
if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i];
}
return par[u][0];
}
vector<pair<int, int>> dat[N];
vector<int> order, inv;
ll st[M];
int lc[M], rc[M], cnt[M], root[N], uk;
map<int, int> gde;
void Add(int &c, int pc, int l, int r, int pos, int x, int y) {
c = ++tsz; st[c] = st[pc] + x; lc[c] = lc[pc]; rc[c] = rc[pc]; cnt[c] = cnt[pc] + y;
if (l == r) return;
int mid = l + r >> 1;
if (pos <= mid) Add(lc[c], lc[pc], l, mid, pos, x, y);
else Add(rc[c], rc[pc], mid + 1, r, pos, x, y);
}
void Find(int a, int b, int c, int l, int r, ll s) {
ll S = st[a] + st[b] - 2 * st[c];
int C = cnt[a] + cnt[b] - 2 * cnt[c];
if (l == r) {
if (S <= s) uk -= C;
return;
}
int mid = l + r >> 1;
ll Sl = st[lc[a]] + st[lc[b]] - 2 * st[lc[c]];
int Cl = cnt[lc[a]] + cnt[lc[b]] - 2 * cnt[lc[c]];
if (Sl < s) {
uk -= Cl;
Find(rc[a], rc[b], rc[c], mid + 1, r, s - Sl);
}
else Find(lc[a], lc[b], lc[c], l, mid, s);
}
void Dfs1(int s, int e) {
for (auto u : g[s]) {
if (u.first == e) continue;
root[u.first] = root[s];
int nesto = u.second;
for (int i = 0; i < dat[nesto].size(); i++) {
auto uu = dat[nesto][i];
Add(root[u.first], root[u.first], 0, psz, inv[uu.second], uu.first, 1);
}
Dfs1(u.first, s);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back({v, i});
g[v].push_back({u, i});
}
Dfs(1, 0);
vector<int> vvv(m);
for (int i = 0; i < m; i++) {
int u;
cin >> u >> vvv[i];
dat[u].push_back({vvv[i], i});
}
order.resize(m);
inv.resize(m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&] (int i, int j) {
return vvv[i] < vvv[j];
});
for (int i = 0; i < m; i++) inv[order[i]] = i;
psz = m - 1;
tsz = 0;
Dfs1(1, 0);
while (q--) {
int s, t, x; ll y;
cin >> s >> t >> x >> y;
int lca = Lca(s, t);
uk = cnt[root[s]] + cnt[root[t]] - 2 * cnt[root[lca]];
Find(root[s], root[t], root[lca], 0, psz, y);
cout << max(x - uk, -1) << en;
}
return 0;
}
Compilation message
currencies.cpp: In function 'void Add(int&, int, int, int, int, int, int)':
currencies.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = l + r >> 1;
| ~~^~~
currencies.cpp: In function 'void Find(int, int, int, int, int, long long int)':
currencies.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = l + r >> 1;
| ~~^~~
currencies.cpp: In function 'void Dfs1(int, int)':
currencies.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < dat[nesto].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
2 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5844 KB |
Output is correct |
6 |
Correct |
6 ms |
5844 KB |
Output is correct |
7 |
Correct |
5 ms |
5588 KB |
Output is correct |
8 |
Correct |
6 ms |
5856 KB |
Output is correct |
9 |
Correct |
6 ms |
5844 KB |
Output is correct |
10 |
Correct |
6 ms |
5844 KB |
Output is correct |
11 |
Correct |
6 ms |
5844 KB |
Output is correct |
12 |
Correct |
6 ms |
5832 KB |
Output is correct |
13 |
Correct |
6 ms |
5988 KB |
Output is correct |
14 |
Correct |
6 ms |
5988 KB |
Output is correct |
15 |
Correct |
6 ms |
5988 KB |
Output is correct |
16 |
Correct |
6 ms |
5844 KB |
Output is correct |
17 |
Correct |
6 ms |
5860 KB |
Output is correct |
18 |
Correct |
6 ms |
5860 KB |
Output is correct |
19 |
Correct |
5 ms |
5860 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
7 ms |
5844 KB |
Output is correct |
22 |
Correct |
5 ms |
5844 KB |
Output is correct |
23 |
Correct |
6 ms |
5916 KB |
Output is correct |
24 |
Correct |
6 ms |
5844 KB |
Output is correct |
25 |
Correct |
9 ms |
5860 KB |
Output is correct |
26 |
Correct |
6 ms |
5864 KB |
Output is correct |
27 |
Correct |
7 ms |
5860 KB |
Output is correct |
28 |
Correct |
6 ms |
5908 KB |
Output is correct |
29 |
Correct |
5 ms |
5860 KB |
Output is correct |
30 |
Correct |
7 ms |
5844 KB |
Output is correct |
31 |
Correct |
6 ms |
5816 KB |
Output is correct |
32 |
Correct |
6 ms |
5824 KB |
Output is correct |
33 |
Correct |
6 ms |
6112 KB |
Output is correct |
34 |
Correct |
6 ms |
6108 KB |
Output is correct |
35 |
Correct |
6 ms |
6100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
6 ms |
5844 KB |
Output is correct |
3 |
Correct |
8 ms |
5844 KB |
Output is correct |
4 |
Correct |
6 ms |
5824 KB |
Output is correct |
5 |
Correct |
238 ms |
54980 KB |
Output is correct |
6 |
Correct |
233 ms |
48716 KB |
Output is correct |
7 |
Correct |
224 ms |
43712 KB |
Output is correct |
8 |
Correct |
168 ms |
42212 KB |
Output is correct |
9 |
Correct |
191 ms |
44060 KB |
Output is correct |
10 |
Correct |
272 ms |
59852 KB |
Output is correct |
11 |
Correct |
248 ms |
59936 KB |
Output is correct |
12 |
Correct |
268 ms |
59944 KB |
Output is correct |
13 |
Correct |
287 ms |
59920 KB |
Output is correct |
14 |
Correct |
284 ms |
59980 KB |
Output is correct |
15 |
Correct |
470 ms |
70092 KB |
Output is correct |
16 |
Correct |
448 ms |
71000 KB |
Output is correct |
17 |
Correct |
478 ms |
69616 KB |
Output is correct |
18 |
Correct |
384 ms |
59904 KB |
Output is correct |
19 |
Correct |
352 ms |
59928 KB |
Output is correct |
20 |
Correct |
364 ms |
60124 KB |
Output is correct |
21 |
Correct |
193 ms |
59336 KB |
Output is correct |
22 |
Correct |
211 ms |
59576 KB |
Output is correct |
23 |
Correct |
202 ms |
59624 KB |
Output is correct |
24 |
Correct |
191 ms |
59516 KB |
Output is correct |
25 |
Correct |
256 ms |
59800 KB |
Output is correct |
26 |
Correct |
270 ms |
59924 KB |
Output is correct |
27 |
Correct |
268 ms |
59844 KB |
Output is correct |
28 |
Correct |
206 ms |
59780 KB |
Output is correct |
29 |
Correct |
190 ms |
59804 KB |
Output is correct |
30 |
Correct |
221 ms |
60008 KB |
Output is correct |
31 |
Correct |
226 ms |
59960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
6 ms |
6104 KB |
Output is correct |
3 |
Correct |
6 ms |
6108 KB |
Output is correct |
4 |
Correct |
7 ms |
6100 KB |
Output is correct |
5 |
Correct |
245 ms |
54464 KB |
Output is correct |
6 |
Correct |
265 ms |
48484 KB |
Output is correct |
7 |
Correct |
340 ms |
57112 KB |
Output is correct |
8 |
Correct |
471 ms |
71036 KB |
Output is correct |
9 |
Correct |
390 ms |
71040 KB |
Output is correct |
10 |
Correct |
404 ms |
71096 KB |
Output is correct |
11 |
Correct |
365 ms |
70600 KB |
Output is correct |
12 |
Correct |
333 ms |
70592 KB |
Output is correct |
13 |
Correct |
351 ms |
70736 KB |
Output is correct |
14 |
Correct |
231 ms |
70976 KB |
Output is correct |
15 |
Correct |
246 ms |
70864 KB |
Output is correct |
16 |
Correct |
259 ms |
71116 KB |
Output is correct |
17 |
Correct |
260 ms |
70948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
2 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
5844 KB |
Output is correct |
6 |
Correct |
6 ms |
5844 KB |
Output is correct |
7 |
Correct |
5 ms |
5588 KB |
Output is correct |
8 |
Correct |
6 ms |
5856 KB |
Output is correct |
9 |
Correct |
6 ms |
5844 KB |
Output is correct |
10 |
Correct |
6 ms |
5844 KB |
Output is correct |
11 |
Correct |
6 ms |
5844 KB |
Output is correct |
12 |
Correct |
6 ms |
5832 KB |
Output is correct |
13 |
Correct |
6 ms |
5988 KB |
Output is correct |
14 |
Correct |
6 ms |
5988 KB |
Output is correct |
15 |
Correct |
6 ms |
5988 KB |
Output is correct |
16 |
Correct |
6 ms |
5844 KB |
Output is correct |
17 |
Correct |
6 ms |
5860 KB |
Output is correct |
18 |
Correct |
6 ms |
5860 KB |
Output is correct |
19 |
Correct |
5 ms |
5860 KB |
Output is correct |
20 |
Correct |
5 ms |
5844 KB |
Output is correct |
21 |
Correct |
7 ms |
5844 KB |
Output is correct |
22 |
Correct |
5 ms |
5844 KB |
Output is correct |
23 |
Correct |
6 ms |
5916 KB |
Output is correct |
24 |
Correct |
6 ms |
5844 KB |
Output is correct |
25 |
Correct |
9 ms |
5860 KB |
Output is correct |
26 |
Correct |
6 ms |
5864 KB |
Output is correct |
27 |
Correct |
7 ms |
5860 KB |
Output is correct |
28 |
Correct |
6 ms |
5908 KB |
Output is correct |
29 |
Correct |
5 ms |
5860 KB |
Output is correct |
30 |
Correct |
7 ms |
5844 KB |
Output is correct |
31 |
Correct |
6 ms |
5816 KB |
Output is correct |
32 |
Correct |
6 ms |
5824 KB |
Output is correct |
33 |
Correct |
6 ms |
6112 KB |
Output is correct |
34 |
Correct |
6 ms |
6108 KB |
Output is correct |
35 |
Correct |
6 ms |
6100 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
6 ms |
5844 KB |
Output is correct |
38 |
Correct |
8 ms |
5844 KB |
Output is correct |
39 |
Correct |
6 ms |
5824 KB |
Output is correct |
40 |
Correct |
238 ms |
54980 KB |
Output is correct |
41 |
Correct |
233 ms |
48716 KB |
Output is correct |
42 |
Correct |
224 ms |
43712 KB |
Output is correct |
43 |
Correct |
168 ms |
42212 KB |
Output is correct |
44 |
Correct |
191 ms |
44060 KB |
Output is correct |
45 |
Correct |
272 ms |
59852 KB |
Output is correct |
46 |
Correct |
248 ms |
59936 KB |
Output is correct |
47 |
Correct |
268 ms |
59944 KB |
Output is correct |
48 |
Correct |
287 ms |
59920 KB |
Output is correct |
49 |
Correct |
284 ms |
59980 KB |
Output is correct |
50 |
Correct |
470 ms |
70092 KB |
Output is correct |
51 |
Correct |
448 ms |
71000 KB |
Output is correct |
52 |
Correct |
478 ms |
69616 KB |
Output is correct |
53 |
Correct |
384 ms |
59904 KB |
Output is correct |
54 |
Correct |
352 ms |
59928 KB |
Output is correct |
55 |
Correct |
364 ms |
60124 KB |
Output is correct |
56 |
Correct |
193 ms |
59336 KB |
Output is correct |
57 |
Correct |
211 ms |
59576 KB |
Output is correct |
58 |
Correct |
202 ms |
59624 KB |
Output is correct |
59 |
Correct |
191 ms |
59516 KB |
Output is correct |
60 |
Correct |
256 ms |
59800 KB |
Output is correct |
61 |
Correct |
270 ms |
59924 KB |
Output is correct |
62 |
Correct |
268 ms |
59844 KB |
Output is correct |
63 |
Correct |
206 ms |
59780 KB |
Output is correct |
64 |
Correct |
190 ms |
59804 KB |
Output is correct |
65 |
Correct |
221 ms |
60008 KB |
Output is correct |
66 |
Correct |
226 ms |
59960 KB |
Output is correct |
67 |
Correct |
4 ms |
4948 KB |
Output is correct |
68 |
Correct |
6 ms |
6104 KB |
Output is correct |
69 |
Correct |
6 ms |
6108 KB |
Output is correct |
70 |
Correct |
7 ms |
6100 KB |
Output is correct |
71 |
Correct |
245 ms |
54464 KB |
Output is correct |
72 |
Correct |
265 ms |
48484 KB |
Output is correct |
73 |
Correct |
340 ms |
57112 KB |
Output is correct |
74 |
Correct |
471 ms |
71036 KB |
Output is correct |
75 |
Correct |
390 ms |
71040 KB |
Output is correct |
76 |
Correct |
404 ms |
71096 KB |
Output is correct |
77 |
Correct |
365 ms |
70600 KB |
Output is correct |
78 |
Correct |
333 ms |
70592 KB |
Output is correct |
79 |
Correct |
351 ms |
70736 KB |
Output is correct |
80 |
Correct |
231 ms |
70976 KB |
Output is correct |
81 |
Correct |
246 ms |
70864 KB |
Output is correct |
82 |
Correct |
259 ms |
71116 KB |
Output is correct |
83 |
Correct |
260 ms |
70948 KB |
Output is correct |
84 |
Correct |
208 ms |
54352 KB |
Output is correct |
85 |
Correct |
196 ms |
47204 KB |
Output is correct |
86 |
Correct |
179 ms |
36472 KB |
Output is correct |
87 |
Correct |
279 ms |
59860 KB |
Output is correct |
88 |
Correct |
276 ms |
59276 KB |
Output is correct |
89 |
Correct |
267 ms |
59876 KB |
Output is correct |
90 |
Correct |
310 ms |
59804 KB |
Output is correct |
91 |
Correct |
267 ms |
59780 KB |
Output is correct |
92 |
Correct |
469 ms |
67044 KB |
Output is correct |
93 |
Correct |
446 ms |
69300 KB |
Output is correct |
94 |
Correct |
380 ms |
60048 KB |
Output is correct |
95 |
Correct |
376 ms |
59952 KB |
Output is correct |
96 |
Correct |
395 ms |
59908 KB |
Output is correct |
97 |
Correct |
383 ms |
59936 KB |
Output is correct |
98 |
Correct |
198 ms |
59564 KB |
Output is correct |
99 |
Correct |
196 ms |
59496 KB |
Output is correct |
100 |
Correct |
194 ms |
59300 KB |
Output is correct |
101 |
Correct |
199 ms |
59492 KB |
Output is correct |
102 |
Correct |
265 ms |
59792 KB |
Output is correct |
103 |
Correct |
271 ms |
59864 KB |
Output is correct |
104 |
Correct |
259 ms |
59728 KB |
Output is correct |
105 |
Correct |
219 ms |
60008 KB |
Output is correct |
106 |
Correct |
210 ms |
59572 KB |
Output is correct |
107 |
Correct |
203 ms |
59820 KB |
Output is correct |
108 |
Correct |
202 ms |
59728 KB |
Output is correct |