#include <bits/stdc++.h>
using namespace std;
int64_t f[100000], af[100000];
void update(int p, int x) {
while (p < 100000) {
f[p] += x;
p |= p + 1;
}
}
int64_t query(int p) {
int64_t res = 0;
while (p >= 0) {
res += f[p];
p = (p & (p + 1)) - 1;
}
return res;
}
void update(int p, int x, int y) {
while (p < 100000) {
f[p] += x;
af[p] += y;
p |= p + 1;
}
}
pair<int64_t, int> duo_query(int p) {
pair<int64_t, int> res{0, 0};
while (p >= 0) {
res.first += f[p];
res.second += af[p];
p = (p & (p + 1)) - 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> ce(n - 1);
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u -= 1;
v -= 1;
adj[u].emplace_back(i);
adj[v].emplace_back(i);
ce[i] = u ^ v;
}
vector<int> cv;
vector<pair<int, int>> cp(m);
for (int i = 0; i < m; i++) {
int u, x;
cin >> u >> x;
u -= 1;
cp[i] = make_pair(u, x);
cv.emplace_back(x);
}
sort(cv.begin(), cv.end());
cv.erase(unique(cv.begin(), cv.end()), cv.end());
vector<int> dfn(n), size(n), top(n), depth(n), parent(n), c(n - 1);
{
function<void(int)> dfs = [&](int u) -> void {
size[u] = 1;
for (int &i : adj[u]) {
int v = ce[i] ^ u;
adj[v].erase(find(adj[v].begin(), adj[v].end(), i));
c[i] = v;
dfs(v);
size[u] += size[v];
if (size[v] > size[ce[adj[u][0]] ^ u]) {
swap(adj[u][0], i);
}
}
};
dfs(0);
int t = 0;
dfs = [&](int u) -> void {
dfn[u] = t++;
for (int i : adj[u]) {
int v = ce[i] ^ u;
top[v] = (i == adj[u][0] ? top[u] : v);
depth[v] = depth[u] + 1;
parent[v] = u;
dfs(v);
}
};
dfs(0);
parent[0] = -1;
}
int k = cv.size();
vector<vector<int>> ev(k);
for (auto [u, x] : cp) {
u = c[u];
x = lower_bound(cv.begin(), cv.end(), x) - cv.begin();
ev[x].emplace_back(u);
update(dfn[u], 1);
}
vector<int> s(q), t(q), x(q);
vector<int64_t> y(q);
for (int i = 0; i < q; i++) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
s[i] -= 1;
t[i] -= 1;
}
vector<int> cnt(q);
for (int i = 0; i < q; i++) {
int u = s[i];
int v = t[i];
while (top[u] != top[v]) {
if (depth[top[u]] > depth[top[v]]) {
swap(u, v);
}
cnt[i] += query(dfn[v]) - query(dfn[top[v]] - 1);
v = parent[top[v]];
}
if (depth[u] > depth[v]) {
swap(u, v);
}
cnt[i] += query(dfn[v]) - query(dfn[u]);
}
vector<int> mxa(q), last(q, -1);
vector<int64_t> rem = y;
vector<pair<int, int>> bs(q, make_pair(0, k));
while (true) {
bool fin = true;
vector<vector<int>> qr(k);
for (int i = 0; i < q; i++) {
if (bs[i].first < bs[i].second) {
int p = (bs[i].first + bs[i].second) / 2;
qr[p].emplace_back(i);
fin = false;
}
}
if (fin) {
break;
}
memset(f, 0, sizeof(f));
memset(af, 0, sizeof(af));
for (int i = 0; i < k; i++) {
for (int u : ev[i]) {
update(dfn[u], cv[i], 1);
}
for (int qi : qr[i]) {
int u = s[qi];
int v = t[qi];
int64_t sum = 0;
int num = 0;
while (top[u] != top[v]) {
if (depth[top[u]] > depth[top[v]]) {
swap(u, v);
}
auto [sum1, num1] = duo_query(dfn[v]);
auto [sum2, num2] = duo_query(dfn[top[v]] - 1);
sum += sum1 - sum2;
num += num1 - num2;
v = parent[top[v]];
}
if (depth[u] > depth[v]) {
swap(u, v);
}
auto [sum1, num1] = duo_query(dfn[v]);
auto [sum2, num2] = duo_query(dfn[u]);
sum += sum1 - sum2;
num += num1 - num2;
if (sum <= y[qi]) {
mxa[qi] = num;
last[qi] = i;
rem[qi] = y[qi] - sum;
bs[qi].first = i + 1;
}
else {
bs[qi].second = i;
}
}
}
}
for (int i = 0; i < q; i++) {
if (last[i] + 1 < k) {
x[i] -= (cnt[i] - mxa[i] - rem[i] / cv[last[i] + 1]);
}
x[i] = max(x[i], -1);
cout << x[i] << " \n"[i == n - 1];
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
6 ms |
2268 KB |
Output is correct |
6 |
Correct |
8 ms |
2476 KB |
Output is correct |
7 |
Correct |
6 ms |
2396 KB |
Output is correct |
8 |
Correct |
8 ms |
2480 KB |
Output is correct |
9 |
Correct |
8 ms |
2580 KB |
Output is correct |
10 |
Correct |
8 ms |
2396 KB |
Output is correct |
11 |
Correct |
8 ms |
2460 KB |
Output is correct |
12 |
Correct |
8 ms |
2396 KB |
Output is correct |
13 |
Correct |
5 ms |
2652 KB |
Output is correct |
14 |
Correct |
6 ms |
2652 KB |
Output is correct |
15 |
Correct |
6 ms |
2652 KB |
Output is correct |
16 |
Correct |
6 ms |
2652 KB |
Output is correct |
17 |
Correct |
7 ms |
2396 KB |
Output is correct |
18 |
Correct |
6 ms |
2648 KB |
Output is correct |
19 |
Correct |
6 ms |
2648 KB |
Output is correct |
20 |
Correct |
6 ms |
2396 KB |
Output is correct |
21 |
Correct |
6 ms |
2396 KB |
Output is correct |
22 |
Correct |
6 ms |
2396 KB |
Output is correct |
23 |
Correct |
7 ms |
2396 KB |
Output is correct |
24 |
Correct |
7 ms |
2368 KB |
Output is correct |
25 |
Correct |
7 ms |
2392 KB |
Output is correct |
26 |
Correct |
5 ms |
2396 KB |
Output is correct |
27 |
Correct |
5 ms |
2396 KB |
Output is correct |
28 |
Correct |
6 ms |
2396 KB |
Output is correct |
29 |
Correct |
5 ms |
2528 KB |
Output is correct |
30 |
Correct |
3 ms |
2396 KB |
Output is correct |
31 |
Correct |
3 ms |
2396 KB |
Output is correct |
32 |
Correct |
3 ms |
2396 KB |
Output is correct |
33 |
Correct |
5 ms |
2788 KB |
Output is correct |
34 |
Correct |
5 ms |
2652 KB |
Output is correct |
35 |
Correct |
5 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
3 ms |
2396 KB |
Output is correct |
3 |
Correct |
3 ms |
2392 KB |
Output is correct |
4 |
Correct |
3 ms |
2392 KB |
Output is correct |
5 |
Correct |
129 ms |
19420 KB |
Output is correct |
6 |
Correct |
163 ms |
19020 KB |
Output is correct |
7 |
Correct |
150 ms |
19444 KB |
Output is correct |
8 |
Correct |
125 ms |
17716 KB |
Output is correct |
9 |
Correct |
118 ms |
17520 KB |
Output is correct |
10 |
Correct |
185 ms |
22360 KB |
Output is correct |
11 |
Correct |
174 ms |
22184 KB |
Output is correct |
12 |
Correct |
176 ms |
22216 KB |
Output is correct |
13 |
Correct |
184 ms |
22260 KB |
Output is correct |
14 |
Correct |
171 ms |
22252 KB |
Output is correct |
15 |
Correct |
114 ms |
32844 KB |
Output is correct |
16 |
Correct |
114 ms |
33416 KB |
Output is correct |
17 |
Correct |
112 ms |
32328 KB |
Output is correct |
18 |
Correct |
158 ms |
22604 KB |
Output is correct |
19 |
Correct |
143 ms |
22596 KB |
Output is correct |
20 |
Correct |
149 ms |
22820 KB |
Output is correct |
21 |
Correct |
95 ms |
21844 KB |
Output is correct |
22 |
Correct |
95 ms |
22028 KB |
Output is correct |
23 |
Correct |
98 ms |
22096 KB |
Output is correct |
24 |
Correct |
95 ms |
22100 KB |
Output is correct |
25 |
Correct |
146 ms |
22592 KB |
Output is correct |
26 |
Correct |
163 ms |
22504 KB |
Output is correct |
27 |
Correct |
143 ms |
22620 KB |
Output is correct |
28 |
Correct |
109 ms |
21960 KB |
Output is correct |
29 |
Correct |
121 ms |
22092 KB |
Output is correct |
30 |
Correct |
144 ms |
22204 KB |
Output is correct |
31 |
Correct |
124 ms |
22228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2136 KB |
Output is correct |
2 |
Correct |
5 ms |
2904 KB |
Output is correct |
3 |
Correct |
5 ms |
2652 KB |
Output is correct |
4 |
Correct |
5 ms |
2652 KB |
Output is correct |
5 |
Correct |
237 ms |
34772 KB |
Output is correct |
6 |
Correct |
212 ms |
32920 KB |
Output is correct |
7 |
Correct |
320 ms |
31304 KB |
Output is correct |
8 |
Correct |
382 ms |
42176 KB |
Output is correct |
9 |
Correct |
389 ms |
42408 KB |
Output is correct |
10 |
Correct |
392 ms |
42188 KB |
Output is correct |
11 |
Correct |
342 ms |
42392 KB |
Output is correct |
12 |
Correct |
347 ms |
42132 KB |
Output is correct |
13 |
Correct |
340 ms |
42388 KB |
Output is correct |
14 |
Correct |
321 ms |
41844 KB |
Output is correct |
15 |
Correct |
285 ms |
41872 KB |
Output is correct |
16 |
Correct |
324 ms |
42000 KB |
Output is correct |
17 |
Correct |
312 ms |
42512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
6 ms |
2268 KB |
Output is correct |
6 |
Correct |
8 ms |
2476 KB |
Output is correct |
7 |
Correct |
6 ms |
2396 KB |
Output is correct |
8 |
Correct |
8 ms |
2480 KB |
Output is correct |
9 |
Correct |
8 ms |
2580 KB |
Output is correct |
10 |
Correct |
8 ms |
2396 KB |
Output is correct |
11 |
Correct |
8 ms |
2460 KB |
Output is correct |
12 |
Correct |
8 ms |
2396 KB |
Output is correct |
13 |
Correct |
5 ms |
2652 KB |
Output is correct |
14 |
Correct |
6 ms |
2652 KB |
Output is correct |
15 |
Correct |
6 ms |
2652 KB |
Output is correct |
16 |
Correct |
6 ms |
2652 KB |
Output is correct |
17 |
Correct |
7 ms |
2396 KB |
Output is correct |
18 |
Correct |
6 ms |
2648 KB |
Output is correct |
19 |
Correct |
6 ms |
2648 KB |
Output is correct |
20 |
Correct |
6 ms |
2396 KB |
Output is correct |
21 |
Correct |
6 ms |
2396 KB |
Output is correct |
22 |
Correct |
6 ms |
2396 KB |
Output is correct |
23 |
Correct |
7 ms |
2396 KB |
Output is correct |
24 |
Correct |
7 ms |
2368 KB |
Output is correct |
25 |
Correct |
7 ms |
2392 KB |
Output is correct |
26 |
Correct |
5 ms |
2396 KB |
Output is correct |
27 |
Correct |
5 ms |
2396 KB |
Output is correct |
28 |
Correct |
6 ms |
2396 KB |
Output is correct |
29 |
Correct |
5 ms |
2528 KB |
Output is correct |
30 |
Correct |
3 ms |
2396 KB |
Output is correct |
31 |
Correct |
3 ms |
2396 KB |
Output is correct |
32 |
Correct |
3 ms |
2396 KB |
Output is correct |
33 |
Correct |
5 ms |
2788 KB |
Output is correct |
34 |
Correct |
5 ms |
2652 KB |
Output is correct |
35 |
Correct |
5 ms |
2652 KB |
Output is correct |
36 |
Correct |
1 ms |
1884 KB |
Output is correct |
37 |
Correct |
3 ms |
2396 KB |
Output is correct |
38 |
Correct |
3 ms |
2392 KB |
Output is correct |
39 |
Correct |
3 ms |
2392 KB |
Output is correct |
40 |
Correct |
129 ms |
19420 KB |
Output is correct |
41 |
Correct |
163 ms |
19020 KB |
Output is correct |
42 |
Correct |
150 ms |
19444 KB |
Output is correct |
43 |
Correct |
125 ms |
17716 KB |
Output is correct |
44 |
Correct |
118 ms |
17520 KB |
Output is correct |
45 |
Correct |
185 ms |
22360 KB |
Output is correct |
46 |
Correct |
174 ms |
22184 KB |
Output is correct |
47 |
Correct |
176 ms |
22216 KB |
Output is correct |
48 |
Correct |
184 ms |
22260 KB |
Output is correct |
49 |
Correct |
171 ms |
22252 KB |
Output is correct |
50 |
Correct |
114 ms |
32844 KB |
Output is correct |
51 |
Correct |
114 ms |
33416 KB |
Output is correct |
52 |
Correct |
112 ms |
32328 KB |
Output is correct |
53 |
Correct |
158 ms |
22604 KB |
Output is correct |
54 |
Correct |
143 ms |
22596 KB |
Output is correct |
55 |
Correct |
149 ms |
22820 KB |
Output is correct |
56 |
Correct |
95 ms |
21844 KB |
Output is correct |
57 |
Correct |
95 ms |
22028 KB |
Output is correct |
58 |
Correct |
98 ms |
22096 KB |
Output is correct |
59 |
Correct |
95 ms |
22100 KB |
Output is correct |
60 |
Correct |
146 ms |
22592 KB |
Output is correct |
61 |
Correct |
163 ms |
22504 KB |
Output is correct |
62 |
Correct |
143 ms |
22620 KB |
Output is correct |
63 |
Correct |
109 ms |
21960 KB |
Output is correct |
64 |
Correct |
121 ms |
22092 KB |
Output is correct |
65 |
Correct |
144 ms |
22204 KB |
Output is correct |
66 |
Correct |
124 ms |
22228 KB |
Output is correct |
67 |
Correct |
1 ms |
2136 KB |
Output is correct |
68 |
Correct |
5 ms |
2904 KB |
Output is correct |
69 |
Correct |
5 ms |
2652 KB |
Output is correct |
70 |
Correct |
5 ms |
2652 KB |
Output is correct |
71 |
Correct |
237 ms |
34772 KB |
Output is correct |
72 |
Correct |
212 ms |
32920 KB |
Output is correct |
73 |
Correct |
320 ms |
31304 KB |
Output is correct |
74 |
Correct |
382 ms |
42176 KB |
Output is correct |
75 |
Correct |
389 ms |
42408 KB |
Output is correct |
76 |
Correct |
392 ms |
42188 KB |
Output is correct |
77 |
Correct |
342 ms |
42392 KB |
Output is correct |
78 |
Correct |
347 ms |
42132 KB |
Output is correct |
79 |
Correct |
340 ms |
42388 KB |
Output is correct |
80 |
Correct |
321 ms |
41844 KB |
Output is correct |
81 |
Correct |
285 ms |
41872 KB |
Output is correct |
82 |
Correct |
324 ms |
42000 KB |
Output is correct |
83 |
Correct |
312 ms |
42512 KB |
Output is correct |
84 |
Correct |
708 ms |
25404 KB |
Output is correct |
85 |
Correct |
747 ms |
22880 KB |
Output is correct |
86 |
Correct |
694 ms |
20088 KB |
Output is correct |
87 |
Correct |
1088 ms |
30356 KB |
Output is correct |
88 |
Correct |
1117 ms |
30608 KB |
Output is correct |
89 |
Correct |
1093 ms |
30176 KB |
Output is correct |
90 |
Correct |
1089 ms |
30360 KB |
Output is correct |
91 |
Correct |
1083 ms |
30316 KB |
Output is correct |
92 |
Correct |
499 ms |
38040 KB |
Output is correct |
93 |
Correct |
450 ms |
40340 KB |
Output is correct |
94 |
Correct |
994 ms |
31068 KB |
Output is correct |
95 |
Correct |
913 ms |
31016 KB |
Output is correct |
96 |
Correct |
828 ms |
30996 KB |
Output is correct |
97 |
Correct |
805 ms |
30960 KB |
Output is correct |
98 |
Correct |
432 ms |
30368 KB |
Output is correct |
99 |
Correct |
461 ms |
30032 KB |
Output is correct |
100 |
Correct |
585 ms |
30480 KB |
Output is correct |
101 |
Correct |
467 ms |
30160 KB |
Output is correct |
102 |
Correct |
769 ms |
30896 KB |
Output is correct |
103 |
Correct |
772 ms |
30904 KB |
Output is correct |
104 |
Correct |
741 ms |
30868 KB |
Output is correct |
105 |
Correct |
442 ms |
30360 KB |
Output is correct |
106 |
Correct |
506 ms |
30300 KB |
Output is correct |
107 |
Correct |
606 ms |
30052 KB |
Output is correct |
108 |
Correct |
502 ms |
30356 KB |
Output is correct |