#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<ll, ll> pii;
const int MAXN = 5e5 + 5;
ll sub_size[MAXN], visited[MAXN], best[MAXN];
vector<pii> adj[MAXN], dis[MAXN];
// Find subtree size.
int subSize(int cur, int par) {
sub_size[cur] = 1;
for (pii next : adj[cur])
if (next.f != par && !visited[next.f])
sub_size[cur] += subSize(next.f, cur);
return sub_size[cur];
}
// Return the centroid.
int findCentroid(int cur, int par, int N) {
for (pii next : adj[cur]) {
if (next.f != par && !visited[next.f] && sub_size[next.f] > N / 2) {
return findCentroid(next.f, cur, N);
}
}
return cur;
}
void getDis(int cur, int par, int c, ll dist) {
dis[cur].pb({ c, dist });
for (pii next : adj[cur]) {
if (next.f != par && !visited[next.f]) {
getDis(next.f, cur, c, dist + next.s);
}
}
}
void build(int cur) {
int centroid = findCentroid(cur, -1, subSize(cur, -1));
getDis(centroid, -1, centroid, 0);
visited[centroid] = 1;
for (pii next : adj[centroid]) {
if (!visited[next.f]) {
build(next.f);
}
}
}
// Initialize function
void Init(int n, int a[], int b[], int c[]) {
// Read edges
for (int i = 0; i < n - 1; i++) {
adj[a[i]].pb({ b[i], c[i] });
adj[b[i]].pb({ a[i], c[i] });
}
build(0);
fill(best, best + MAXN, LINF);
}
// Process queries
ll Query(int len1, int x[], int len2, int y[]) {
ll ans = LINF;
for (int u = 0; u < len1; u++) {
for (pii i : dis[x[u]]) {
best[i.f] = min(best[i.f], i.s);
}
}
for (int u = 0; u < len2; u++) {
for (pii i : dis[y[u]]) {
ans = min(ans, best[i.f] + i.s);
}
}
for (int u = 0; u < len1; u++) {
for (pii i : dis[x[u]]) {
best[i.f] = LINF;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
28232 KB |
Output is correct |
2 |
Correct |
352 ms |
46276 KB |
Output is correct |
3 |
Correct |
373 ms |
46804 KB |
Output is correct |
4 |
Correct |
402 ms |
46760 KB |
Output is correct |
5 |
Correct |
401 ms |
47264 KB |
Output is correct |
6 |
Correct |
281 ms |
45880 KB |
Output is correct |
7 |
Correct |
368 ms |
46788 KB |
Output is correct |
8 |
Correct |
375 ms |
46840 KB |
Output is correct |
9 |
Correct |
401 ms |
47144 KB |
Output is correct |
10 |
Correct |
305 ms |
45876 KB |
Output is correct |
11 |
Correct |
382 ms |
46848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
27852 KB |
Output is correct |
2 |
Correct |
2588 ms |
219792 KB |
Output is correct |
3 |
Correct |
4163 ms |
289816 KB |
Output is correct |
4 |
Correct |
1075 ms |
113448 KB |
Output is correct |
5 |
Correct |
4941 ms |
365292 KB |
Output is correct |
6 |
Correct |
4090 ms |
291144 KB |
Output is correct |
7 |
Correct |
1334 ms |
86964 KB |
Output is correct |
8 |
Correct |
542 ms |
64136 KB |
Output is correct |
9 |
Correct |
1360 ms |
101204 KB |
Output is correct |
10 |
Correct |
1253 ms |
88432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
28232 KB |
Output is correct |
2 |
Correct |
352 ms |
46276 KB |
Output is correct |
3 |
Correct |
373 ms |
46804 KB |
Output is correct |
4 |
Correct |
402 ms |
46760 KB |
Output is correct |
5 |
Correct |
401 ms |
47264 KB |
Output is correct |
6 |
Correct |
281 ms |
45880 KB |
Output is correct |
7 |
Correct |
368 ms |
46788 KB |
Output is correct |
8 |
Correct |
375 ms |
46840 KB |
Output is correct |
9 |
Correct |
401 ms |
47144 KB |
Output is correct |
10 |
Correct |
305 ms |
45876 KB |
Output is correct |
11 |
Correct |
382 ms |
46848 KB |
Output is correct |
12 |
Correct |
17 ms |
27852 KB |
Output is correct |
13 |
Correct |
2588 ms |
219792 KB |
Output is correct |
14 |
Correct |
4163 ms |
289816 KB |
Output is correct |
15 |
Correct |
1075 ms |
113448 KB |
Output is correct |
16 |
Correct |
4941 ms |
365292 KB |
Output is correct |
17 |
Correct |
4090 ms |
291144 KB |
Output is correct |
18 |
Correct |
1334 ms |
86964 KB |
Output is correct |
19 |
Correct |
542 ms |
64136 KB |
Output is correct |
20 |
Correct |
1360 ms |
101204 KB |
Output is correct |
21 |
Correct |
1253 ms |
88432 KB |
Output is correct |
22 |
Correct |
3379 ms |
225024 KB |
Output is correct |
23 |
Correct |
3383 ms |
230012 KB |
Output is correct |
24 |
Correct |
4751 ms |
297512 KB |
Output is correct |
25 |
Correct |
5166 ms |
301480 KB |
Output is correct |
26 |
Correct |
4696 ms |
298248 KB |
Output is correct |
27 |
Correct |
5543 ms |
371832 KB |
Output is correct |
28 |
Correct |
1532 ms |
123872 KB |
Output is correct |
29 |
Correct |
4787 ms |
297588 KB |
Output is correct |
30 |
Correct |
4846 ms |
297856 KB |
Output is correct |
31 |
Correct |
4780 ms |
297744 KB |
Output is correct |
32 |
Correct |
1565 ms |
101704 KB |
Output is correct |
33 |
Correct |
654 ms |
64648 KB |
Output is correct |
34 |
Correct |
1033 ms |
79584 KB |
Output is correct |
35 |
Correct |
1037 ms |
80248 KB |
Output is correct |
36 |
Correct |
1274 ms |
85524 KB |
Output is correct |
37 |
Correct |
1255 ms |
85444 KB |
Output is correct |