#include <iostream>
#include <vector>
#include "factories.h"
using namespace std;
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
const int N = 5e5+2;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[N][20], lvl[N];
ll w[N], cur[N], dis[N][25];
vector<pii> E[N];
void dfs(int nd, int pr){
sub[nd] = 1;
for (auto i : E[nd]){
if (i.ff == pr or rem[i.ff]) continue;
dfs(i.ff, nd);
sub[nd] += sub[i.ff];
}
}
int centroid(int nd, int pr, int sz){
for (auto i : E[nd]){
if (i.ff == pr or rem[i.ff]) continue;
if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
}
return nd;
}
void build(int nd, int pr){
int centr = centroid(nd, 0, sub[nd]);
rem[centr] = 1;
par[centr] = pr;
for (auto i : E[centr]){
if (!rem[i.ff]){
dfs(i.ff, 0);
build(i.ff, centr);
}
}
}
void dfs2(int nd, int pr){
sp[nd][0] = pr;
for (auto i : E[nd]){
if (i.ff == pr) continue;
lvl[i.ff] = lvl[nd]+1;
w[i.ff] = w[nd]+i.ss;
dfs2(i.ff, nd);
}
}
int LCA(int u, int v){
if (lvl[u] < lvl[v]) swap(u, v);
int diff = lvl[u]-lvl[v];
for (int i = 19; i >= 0; i--){
if (diff&(1<<i)) u = sp[u][i];
}
if (u == v) return v;
for (int i = 19; i >= 0; i--){
if (sp[u][i] != sp[v][i]){
u = sp[u][i];
v = sp[v][i];
}
}
return sp[u][0];
}
ll dist(int u, int v){
if (u == v) return 0ll;
return w[u]+w[v]-2*w[LCA(u,v)];
}
void Init(int n, int A[], int B[], int D[]){
for (int i = 0; i < n-1; i++){
A[i]++;
B[i]++;
E[A[i]].pb({B[i], D[i]});
E[B[i]].pb({A[i], D[i]});
}
dfs(1, 0);
build(1, 0);
dfs2(1, 0);
for (int j = 1; j <= 19; j++){
for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1];
}
for (int i = 1; i <= n; i++){
int u = i, k = 0;
while(u){
dis[u][k] = dist(u, i);
k++;
}
}
for (int i = 1; i <= n; i++) cur[i] = inf;
}
void remv(int nd){
while(nd){
cur[nd] = inf;
nd = par[nd];
}
}
void paint(int nd){
int u = nd, k = 0;
while(u){
cur[u] = min(cur[u], dis[u][k]);
u = par[u];
k++;
}
}
ll find(int nd){
ll mn = inf;
int u = nd, k = 0;
while(u){
mn = min(mn, dis[u][k]+cur[u]);
u = par[u];
k++;
}
return mn;
}
ll Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++){
X[i]++;
paint(X[i]);
}
ll ans = inf;
for (int i = 0; i < T; i++){
Y[i]++;
ans = min(ans, find(Y[i]));
}
for (int i = 0; i < S; i++) remv(X[i]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
231 ms |
379208 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
216 ms |
378944 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
231 ms |
379208 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
