#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, Q;
cin >> N >> M >> Q;
vector<pair<int, int>> edges(N - 1);
vector<vector<int>> adj(N);
for (int i = 0; i < N - 1; i++) {
int x, y;
cin >> x >> y;
x--, y--;
edges[i] = {x, y};
adj[x].push_back(i);
adj[y].push_back(i);
}
vector<pair<int, int>> ch(M);
for (int i = 0; i < M; i++) {
int p, c;
cin >> p >> c;
ch[i] = {c, p - 1};
}
sort(ch.begin(), ch.end());
vector<int> t(N - 1);
{
auto dfs = [&](auto dfs, int x, int p) -> void {
for (int z : adj[x]) {
auto [u, v] = edges[z];
int y = x ^ u ^ v;
if (y != p) {
t[z] = y;
dfs(dfs, y, x);
}
}
};
dfs(dfs, 0, -1);
}
for (int i = 0; i < N; i++) {
for (int &j : adj[i]) {
auto [x, y] = edges[j];
j = i ^ x ^ y;
}
}
vector par(N, vector<int>(20, -1));
vector<int> dep(N), sz(N);
auto init = [&](auto init, int x) -> void {
for (int i = 0; i < 19 && par[x][i] != -1; i++) {
par[x][i + 1] = par[par[x][i]][i];
}
if (par[x][0] != -1) {
adj[x].erase(find(adj[x].begin(), adj[x].end(), par[x][0]));
}
sz[x] = 1;
for (int &y : adj[x]) {
par[y][0] = x;
dep[y] = dep[x] + 1;
init(init, y);
sz[x] += sz[y];
if (sz[y] > sz[adj[x][0]]) {
swap(y, adj[x][0]);
}
}
};
init(init, 0);
vector<int> top(N), in(N);
int timer = 0;
auto dfs = [&](auto dfs, int x) -> void {
in[x] = timer++;
for (int y : adj[x]) {
top[y] = adj[x][0] == y ? top[x] : y;
dfs(dfs, y);
}
};
dfs(dfs, 0);
auto lca = [&](int x, int y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
for (int i = 0; i < 20; i++) {
if ((dep[x] - dep[y]) >> i & 1) {
x = par[x][i];
}
}
if (x == y) {
return x;
}
for (int i = 19; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
};
vector<int> S(Q), T(Q), X(Q);
vector<ll> Y(Q);
for (int i = 0; i < Q; i++) {
cin >> S[i] >> T[i] >> X[i] >> Y[i];
S[i]--, T[i]--;
if (S[i] > T[i]) {
swap(S[i], T[i]);
}
}
vector<int> lo(Q), hi(Q, M);
vector<ll> bit(N);
auto add = [&](int i, int v) {
for (i++; i < N; i += i & -i) {
bit[i] += v;
}
};
auto sum = [&](int i) {
ll s = 0;
for (; i; i -= i & -i) {
s += bit[i];
}
return s;
};
vector<ll> s(N);
auto get = [&](int S, int T) {
ll ans = 0;
int P = lca(S, T);
while (S != P) {
ans += s[S];
S = par[S][0];
}
while (T != P) {
ans += s[T];
T = par[T][0];
}
return ans;
};
for (int z = 0; z < 20; z++) {
vector<int> mi(Q);
vector<vector<int>> f(M);
for (int i = 0; i < Q; i++) {
if (lo[i] != hi[i]) {
mi[i] = (lo[i] + hi[i] + 1) / 2;
f[mi[i] - 1].push_back(i);
}
}
s.assign(N, 0);
for (int i = 0; i < M; i++) {
auto [c, p] = ch[i];
s[t[p]] += c;
for (int j : f[i]) {
if (get(S[j], T[j]) <= Y[j]) {
lo[j] = i + 1;
} else {
hi[j] = i;
}
}
}
}
vector<ll> ans(Q);
vector<vector<int>> f(M + 1);
for (int i = 0; i < Q; i++) {
f[lo[i]].push_back(i);
}
s.assign(N, 0);
for (int i = M; i >= 0; i--) {
if (i < M) {
auto [c, p] = ch[i];
s[t[p]]++;
}
for (int j : f[i]) {
ans[j] = max(-1LL, X[j] - get(S[j], T[j]));
}
}
for (int i = 0; i < Q; i++) {
cout << ans[i] << "\n";
}
return 6/22;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:108:10: warning: variable 'add' set but not used [-Wunused-but-set-variable]
108 | auto add = [&](int i, int v) {
| ^~~
currencies.cpp:113:10: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
113 | auto sum = [&](int i) {
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
4 ms |
852 KB |
Output is correct |
6 |
Correct |
6 ms |
980 KB |
Output is correct |
7 |
Correct |
5 ms |
724 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
7 ms |
1020 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
972 KB |
Output is correct |
12 |
Correct |
6 ms |
1020 KB |
Output is correct |
13 |
Correct |
159 ms |
1108 KB |
Output is correct |
14 |
Correct |
144 ms |
1112 KB |
Output is correct |
15 |
Correct |
66 ms |
1100 KB |
Output is correct |
16 |
Correct |
51 ms |
1036 KB |
Output is correct |
17 |
Correct |
41 ms |
980 KB |
Output is correct |
18 |
Correct |
65 ms |
1040 KB |
Output is correct |
19 |
Correct |
4 ms |
980 KB |
Output is correct |
20 |
Correct |
4 ms |
980 KB |
Output is correct |
21 |
Correct |
4 ms |
980 KB |
Output is correct |
22 |
Correct |
4 ms |
980 KB |
Output is correct |
23 |
Correct |
6 ms |
972 KB |
Output is correct |
24 |
Correct |
6 ms |
980 KB |
Output is correct |
25 |
Correct |
6 ms |
1000 KB |
Output is correct |
26 |
Correct |
4 ms |
1028 KB |
Output is correct |
27 |
Correct |
4 ms |
980 KB |
Output is correct |
28 |
Correct |
5 ms |
980 KB |
Output is correct |
29 |
Correct |
4 ms |
980 KB |
Output is correct |
30 |
Correct |
6 ms |
972 KB |
Output is correct |
31 |
Correct |
6 ms |
992 KB |
Output is correct |
32 |
Correct |
6 ms |
972 KB |
Output is correct |
33 |
Correct |
67 ms |
1300 KB |
Output is correct |
34 |
Correct |
67 ms |
1240 KB |
Output is correct |
35 |
Correct |
65 ms |
1176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
6 ms |
980 KB |
Output is correct |
3 |
Correct |
6 ms |
968 KB |
Output is correct |
4 |
Correct |
6 ms |
972 KB |
Output is correct |
5 |
Correct |
911 ms |
29784 KB |
Output is correct |
6 |
Correct |
957 ms |
23776 KB |
Output is correct |
7 |
Correct |
1027 ms |
25652 KB |
Output is correct |
8 |
Correct |
715 ms |
25452 KB |
Output is correct |
9 |
Correct |
822 ms |
25340 KB |
Output is correct |
10 |
Correct |
1248 ms |
31868 KB |
Output is correct |
11 |
Correct |
1299 ms |
31840 KB |
Output is correct |
12 |
Correct |
1376 ms |
31848 KB |
Output is correct |
13 |
Correct |
1336 ms |
31884 KB |
Output is correct |
14 |
Correct |
1295 ms |
31852 KB |
Output is correct |
15 |
Execution timed out |
5043 ms |
37448 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
65 ms |
1180 KB |
Output is correct |
3 |
Correct |
65 ms |
1164 KB |
Output is correct |
4 |
Correct |
65 ms |
1172 KB |
Output is correct |
5 |
Execution timed out |
5077 ms |
34516 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
4 ms |
852 KB |
Output is correct |
6 |
Correct |
6 ms |
980 KB |
Output is correct |
7 |
Correct |
5 ms |
724 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
7 ms |
1020 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
972 KB |
Output is correct |
12 |
Correct |
6 ms |
1020 KB |
Output is correct |
13 |
Correct |
159 ms |
1108 KB |
Output is correct |
14 |
Correct |
144 ms |
1112 KB |
Output is correct |
15 |
Correct |
66 ms |
1100 KB |
Output is correct |
16 |
Correct |
51 ms |
1036 KB |
Output is correct |
17 |
Correct |
41 ms |
980 KB |
Output is correct |
18 |
Correct |
65 ms |
1040 KB |
Output is correct |
19 |
Correct |
4 ms |
980 KB |
Output is correct |
20 |
Correct |
4 ms |
980 KB |
Output is correct |
21 |
Correct |
4 ms |
980 KB |
Output is correct |
22 |
Correct |
4 ms |
980 KB |
Output is correct |
23 |
Correct |
6 ms |
972 KB |
Output is correct |
24 |
Correct |
6 ms |
980 KB |
Output is correct |
25 |
Correct |
6 ms |
1000 KB |
Output is correct |
26 |
Correct |
4 ms |
1028 KB |
Output is correct |
27 |
Correct |
4 ms |
980 KB |
Output is correct |
28 |
Correct |
5 ms |
980 KB |
Output is correct |
29 |
Correct |
4 ms |
980 KB |
Output is correct |
30 |
Correct |
6 ms |
972 KB |
Output is correct |
31 |
Correct |
6 ms |
992 KB |
Output is correct |
32 |
Correct |
6 ms |
972 KB |
Output is correct |
33 |
Correct |
67 ms |
1300 KB |
Output is correct |
34 |
Correct |
67 ms |
1240 KB |
Output is correct |
35 |
Correct |
65 ms |
1176 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
6 ms |
980 KB |
Output is correct |
38 |
Correct |
6 ms |
968 KB |
Output is correct |
39 |
Correct |
6 ms |
972 KB |
Output is correct |
40 |
Correct |
911 ms |
29784 KB |
Output is correct |
41 |
Correct |
957 ms |
23776 KB |
Output is correct |
42 |
Correct |
1027 ms |
25652 KB |
Output is correct |
43 |
Correct |
715 ms |
25452 KB |
Output is correct |
44 |
Correct |
822 ms |
25340 KB |
Output is correct |
45 |
Correct |
1248 ms |
31868 KB |
Output is correct |
46 |
Correct |
1299 ms |
31840 KB |
Output is correct |
47 |
Correct |
1376 ms |
31848 KB |
Output is correct |
48 |
Correct |
1336 ms |
31884 KB |
Output is correct |
49 |
Correct |
1295 ms |
31852 KB |
Output is correct |
50 |
Execution timed out |
5043 ms |
37448 KB |
Time limit exceeded |
51 |
Halted |
0 ms |
0 KB |
- |