#include "factories.h"
#include <climits>
#include <vector>
using namespace std;
using ll = long long;
#define int ll
ll const INF = LLONG_MAX / 3;
struct edge {
ll to, dist;
};
ll n;
ll cur_dist = 0;
vector<vector<edge>> ancestors;
vector<vector<edge>> graph;
vector<ll> sz;
vector<char> removed;
vector<ll> min_dist;
void calc_sz(int const cur, int const par) {
sz[cur] = 1;
for (auto const& [neigh, _dist] : graph[cur]) {
if (removed[neigh] || neigh == par)
continue;
calc_sz(neigh, cur);
sz[cur] += sz[neigh];
}
}
int get_centroid(int const cur, int const par, int const tree_sz) {
for (auto const& [neigh, _dist] : graph[cur]) {
if (removed[neigh] || neigh == par)
continue;
if (sz[neigh] > tree_sz / 2)
return get_centroid(neigh, cur, tree_sz);
}
return cur;
}
void calc_ancestors(int const cur, int const par, int const centroid) {
ancestors[cur].push_back({ centroid, cur_dist });
for (auto const& [neigh, dist] : graph[cur]) {
if (removed[neigh] || neigh == par)
continue;
cur_dist += dist;
calc_ancestors(neigh, cur, centroid);
cur_dist -= dist;
}
}
void decompose(int const cur) {
calc_sz(cur, -1);
int const centroid = get_centroid(cur, -1, sz[cur]);
calc_ancestors(centroid, -1, centroid);
removed[centroid] = true;
for (auto const& [neigh, _dist] : graph[centroid]) {
if (removed[neigh])
continue;
decompose(neigh);
}
}
void Init(signed const N, signed a[], signed b[], signed d[]) {
n = N;
graph.resize(n);
sz.resize(n);
removed.resize(n);
ancestors.resize(n);
min_dist.assign(n, INF);
for (int i = 0; i < n - 1; i++) {
graph[a[i]].push_back({ b[i], d[i] });
graph[b[i]].push_back({ a[i], d[i] });
}
decompose(0);
}
ll Query(signed const s, signed x[], signed const t, signed y[]) {
for (int i = 0; i < t; i++) {
int const cur = y[i];
for (auto const& [ancestor, dist] : ancestors[cur]) {
min_dist[ancestor] = min(min_dist[ancestor], dist);
}
}
ll ans = INF;
for (int i = 0; i < s; i++) {
int const cur = x[i];
for (auto const& [ancestor, dist] : ancestors[cur]) {
ans = min(ans, min_dist[ancestor] + dist);
}
}
for (int i = 0; i < t; i++) {
int const cur = y[i];
for (auto const& [ancestor, dist] : ancestors[cur]) {
min_dist[ancestor] = INF;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
856 KB |
Output is correct |
2 |
Correct |
184 ms |
19280 KB |
Output is correct |
3 |
Correct |
210 ms |
19540 KB |
Output is correct |
4 |
Correct |
215 ms |
19540 KB |
Output is correct |
5 |
Correct |
214 ms |
20312 KB |
Output is correct |
6 |
Correct |
137 ms |
18772 KB |
Output is correct |
7 |
Correct |
199 ms |
19692 KB |
Output is correct |
8 |
Correct |
214 ms |
19792 KB |
Output is correct |
9 |
Correct |
211 ms |
20004 KB |
Output is correct |
10 |
Correct |
138 ms |
18692 KB |
Output is correct |
11 |
Correct |
196 ms |
19740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1591 ms |
216388 KB |
Output is correct |
3 |
Correct |
2453 ms |
285924 KB |
Output is correct |
4 |
Correct |
541 ms |
110160 KB |
Output is correct |
5 |
Correct |
2959 ms |
361020 KB |
Output is correct |
6 |
Correct |
2617 ms |
287524 KB |
Output is correct |
7 |
Correct |
515 ms |
64340 KB |
Output is correct |
8 |
Correct |
220 ms |
41404 KB |
Output is correct |
9 |
Correct |
647 ms |
78676 KB |
Output is correct |
10 |
Correct |
595 ms |
65784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
856 KB |
Output is correct |
2 |
Correct |
184 ms |
19280 KB |
Output is correct |
3 |
Correct |
210 ms |
19540 KB |
Output is correct |
4 |
Correct |
215 ms |
19540 KB |
Output is correct |
5 |
Correct |
214 ms |
20312 KB |
Output is correct |
6 |
Correct |
137 ms |
18772 KB |
Output is correct |
7 |
Correct |
199 ms |
19692 KB |
Output is correct |
8 |
Correct |
214 ms |
19792 KB |
Output is correct |
9 |
Correct |
211 ms |
20004 KB |
Output is correct |
10 |
Correct |
138 ms |
18692 KB |
Output is correct |
11 |
Correct |
196 ms |
19740 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1591 ms |
216388 KB |
Output is correct |
14 |
Correct |
2453 ms |
285924 KB |
Output is correct |
15 |
Correct |
541 ms |
110160 KB |
Output is correct |
16 |
Correct |
2959 ms |
361020 KB |
Output is correct |
17 |
Correct |
2617 ms |
287524 KB |
Output is correct |
18 |
Correct |
515 ms |
64340 KB |
Output is correct |
19 |
Correct |
220 ms |
41404 KB |
Output is correct |
20 |
Correct |
647 ms |
78676 KB |
Output is correct |
21 |
Correct |
595 ms |
65784 KB |
Output is correct |
22 |
Correct |
1788 ms |
221552 KB |
Output is correct |
23 |
Correct |
1905 ms |
226640 KB |
Output is correct |
24 |
Correct |
2855 ms |
293712 KB |
Output is correct |
25 |
Correct |
2994 ms |
297852 KB |
Output is correct |
26 |
Correct |
2899 ms |
295016 KB |
Output is correct |
27 |
Correct |
3451 ms |
367416 KB |
Output is correct |
28 |
Correct |
622 ms |
120492 KB |
Output is correct |
29 |
Correct |
2819 ms |
294012 KB |
Output is correct |
30 |
Correct |
2841 ms |
294484 KB |
Output is correct |
31 |
Correct |
2660 ms |
293860 KB |
Output is correct |
32 |
Correct |
701 ms |
79008 KB |
Output is correct |
33 |
Correct |
221 ms |
41876 KB |
Output is correct |
34 |
Correct |
360 ms |
56832 KB |
Output is correct |
35 |
Correct |
397 ms |
57680 KB |
Output is correct |
36 |
Correct |
523 ms |
62600 KB |
Output is correct |
37 |
Correct |
548 ms |
62800 KB |
Output is correct |