#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> >adj[500005];
int sz[500005];
bool used[500005];
long long pl[20][500005];
int pa[500005];
int lv[500005];
long long mn[500005];
int dfssz(int u,int p=-1){
sz[u]=1;
for(auto v:adj[u])if(v.first!=p&&!used[v.first])sz[u]+=dfssz(v.first,u);
return sz[u];
}
int centroid(int u,int rsz,int p=-1){
for(auto v:adj[u])if(v.first!=p&&!used[v.first]&&sz[v.first]>rsz/2)return centroid(v.first,rsz,u);
return u;
}
void dfs(int u,long long d,int lvl,int p=-1){
pl[lvl][u]=d;
for(auto v:adj[u])if(v.first!=p&&!used[v.first])dfs(v.first,d+v.second,lvl+1,u);
}
void decom(int u,int lvl,int p=-1){
u=centroid(u,dfssz(u));
pa[u]=p;
lv[u]=lvl;
used[u]=true;
dfs(u,0,lvl);
for(auto v:adj[u])if(v.first!=p&&!used[v.first])decom(v.first,lvl+1,u);
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N;i++)adj[B[i]].push_back({A[i],D[i]}),adj[A[i]].push_back({B[i],D[i]});
decom(1,1);
for(int i=0;i<=N;i++)mn[i]=LLONG_MAX;
}
long long fans(int x){
long long ans=LLONG_MAX;
while(x!=-1){
ans=min(ans,mn[x]);
x=pa[x];
}
return ans;
}
void upd(int x){
int st=x;
while(x!=-1){
mn[x]=min(mn[x],pl[lv[x]][st]);
x=pa[x];
}
}
void rvupd(int x){
while(x!=-1){
mn[x]=LLONG_MAX;
x=pa[x];
}
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++)upd(X[i]);
long long ans=LLONG_MAX;
for(int i=0;i<T;i++)ans=min(ans,fans(Y[i]));
for(int i=0;i<S;i++)rvupd(X[i]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
74324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
68188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
74324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
