#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define s second
#define f first
#define ll long long
using namespace std;
const int M = 5e5 + 5;
const ll inf = 1e18 + 5;
int parent[M],dep[M];
bool fix[M];
ll dp[M],dis[25][M];
vector <pair <int,ll> > v[M],path;
int findcentroid(int x,int par,int n,int ¢roid,int h){
int s = 1;
for (auto [to,w]: v[x])
if (!fix[to] && to != par) s += findcentroid(to,x,n,centroid,h);
if (centroid==-1 && (2*s >= n || par == -1)) centroid = x;
return s;
}
void dfs(int x,int par,int h){
for (auto [to,w]: v[x]){
if (!fix[to] && to != par){
dis[h][to] = dis[h][x] + w;
dfs(to,x,h);
}
}
}
void build(int x,int par,int n,int h){
int centroid = -1; ll edge_weight = 0;
findcentroid(x,-1,n,centroid,h);
fix[centroid] = 1;
parent[centroid] = par;
dep[centroid] = h;
dfs(centroid,-1,h);
for (auto [to,w]: v[centroid])
if (!fix[to]) build(to,centroid,n/2,h + 1);
}
void Init(int n, int A[], int B[], int D[]) {
for (int i=0;i<n-1;i++){
v[A[i] + 1].pb({B[i] + 1,D[i]});
v[B[i] + 1].pb({A[i] + 1,D[i]});
}
for (int i = 1; i <= n; i++) dp[i] = inf;
build(1,-1,n,1);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
vector <int> v; v.clear();
for (int i=0;i<S;i++){
X[i]++;
int x = X[i];
while (x != -1){
dp[x] = min(dp[x], dis[dep[x]][X[i]]);
v.pb(x);
x = parent[x];
}
}
for (int i=0;i<T;i++){
Y[i]++;
int y = Y[i];
while (y != -1){
ans = min(ans,dis[dep[y]][Y[i]] + dp[y]);
y = parent[y];
}
}
for (int x: v) dp[x] = inf;
return ans;
}
Compilation message
factories.cpp: In function 'void build(int, int, int, int)':
factories.cpp:33:24: warning: unused variable 'edge_weight' [-Wunused-variable]
33 | int centroid = -1; ll edge_weight = 0;
| ^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
12628 KB |
Output is correct |
2 |
Correct |
314 ms |
30532 KB |
Output is correct |
3 |
Correct |
334 ms |
30592 KB |
Output is correct |
4 |
Correct |
343 ms |
30904 KB |
Output is correct |
5 |
Correct |
347 ms |
31096 KB |
Output is correct |
6 |
Correct |
201 ms |
30060 KB |
Output is correct |
7 |
Correct |
340 ms |
30504 KB |
Output is correct |
8 |
Correct |
348 ms |
30664 KB |
Output is correct |
9 |
Correct |
398 ms |
31064 KB |
Output is correct |
10 |
Correct |
201 ms |
29976 KB |
Output is correct |
11 |
Correct |
364 ms |
30548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12244 KB |
Output is correct |
2 |
Correct |
2172 ms |
146892 KB |
Output is correct |
3 |
Correct |
3071 ms |
151180 KB |
Output is correct |
4 |
Correct |
676 ms |
78688 KB |
Output is correct |
5 |
Correct |
3563 ms |
181156 KB |
Output is correct |
6 |
Correct |
3003 ms |
152008 KB |
Output is correct |
7 |
Correct |
1022 ms |
56708 KB |
Output is correct |
8 |
Correct |
330 ms |
44724 KB |
Output is correct |
9 |
Correct |
1150 ms |
61456 KB |
Output is correct |
10 |
Correct |
1036 ms |
58120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
12628 KB |
Output is correct |
2 |
Correct |
314 ms |
30532 KB |
Output is correct |
3 |
Correct |
334 ms |
30592 KB |
Output is correct |
4 |
Correct |
343 ms |
30904 KB |
Output is correct |
5 |
Correct |
347 ms |
31096 KB |
Output is correct |
6 |
Correct |
201 ms |
30060 KB |
Output is correct |
7 |
Correct |
340 ms |
30504 KB |
Output is correct |
8 |
Correct |
348 ms |
30664 KB |
Output is correct |
9 |
Correct |
398 ms |
31064 KB |
Output is correct |
10 |
Correct |
201 ms |
29976 KB |
Output is correct |
11 |
Correct |
364 ms |
30548 KB |
Output is correct |
12 |
Correct |
9 ms |
12244 KB |
Output is correct |
13 |
Correct |
2172 ms |
146892 KB |
Output is correct |
14 |
Correct |
3071 ms |
151180 KB |
Output is correct |
15 |
Correct |
676 ms |
78688 KB |
Output is correct |
16 |
Correct |
3563 ms |
181156 KB |
Output is correct |
17 |
Correct |
3003 ms |
152008 KB |
Output is correct |
18 |
Correct |
1022 ms |
56708 KB |
Output is correct |
19 |
Correct |
330 ms |
44724 KB |
Output is correct |
20 |
Correct |
1150 ms |
61456 KB |
Output is correct |
21 |
Correct |
1036 ms |
58120 KB |
Output is correct |
22 |
Correct |
2560 ms |
144472 KB |
Output is correct |
23 |
Correct |
2646 ms |
151392 KB |
Output is correct |
24 |
Correct |
3649 ms |
149860 KB |
Output is correct |
25 |
Correct |
3921 ms |
151056 KB |
Output is correct |
26 |
Correct |
3813 ms |
142748 KB |
Output is correct |
27 |
Correct |
4328 ms |
173208 KB |
Output is correct |
28 |
Correct |
734 ms |
72640 KB |
Output is correct |
29 |
Correct |
3580 ms |
142148 KB |
Output is correct |
30 |
Correct |
3870 ms |
141544 KB |
Output is correct |
31 |
Correct |
3693 ms |
142040 KB |
Output is correct |
32 |
Correct |
1335 ms |
67228 KB |
Output is correct |
33 |
Correct |
316 ms |
45848 KB |
Output is correct |
34 |
Correct |
731 ms |
54240 KB |
Output is correct |
35 |
Correct |
751 ms |
54172 KB |
Output is correct |
36 |
Correct |
931 ms |
55124 KB |
Output is correct |
37 |
Correct |
950 ms |
55220 KB |
Output is correct |