#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf=1e18;
int n;
vector<pair<int,ll>> g[500005];
int sz[500005],pac[500005];
bitset<500005> rm(0);
int lv[500005],dp[500005][20];
ll dis[500005][20],dlv[500005],mn[500005];
int szdfs(int u,int p){
sz[u]=1;
for(auto [v,w]:g[u]){
if(v==p||rm[v])
continue;
sz[u]+=szdfs(v,u);
}
return sz[u];
}
int centroid(int u,int p,int ts){
for(auto [v,w]:g[u]){
if(v==p||rm[v])
continue;
if(sz[v]*2>ts)
return centroid(v,u,ts);
}
return u;
}
void build(int u,int p=0){
u=centroid(u,0,szdfs(u,0));
pac[u]=p;
rm[u]=1;
for(auto [v,w]:g[u]){
if(v==p||rm[v])
continue;
build(v,u);
}
}
void pre(int u,int p=0,int l=0,ll d=0){
dp[u][0]=p;
lv[u]=l;
dlv[u]=d;
for(auto [v,w]:g[u]){
if(v==p)
continue;
pre(v,u,l+1,d+w);
}
}
int lca(int a,int b){
if(lv[a]<lv[b])
swap(a,b);
for(int i=19;i>=0;i--){
if(lv[dp[a][i]]>=lv[b])
a=dp[a][i];
}
if(a==b)
return a;
for(int i=19;i>=0;i--){
if(dp[a][i]!=dp[b][i])
a=dp[a][i],b=dp[b][i];
}
return dp[a][0];
}
ll dist(int a,int b){
return dlv[a]+dlv[b]-2*dlv[lca(a,b)];
}
void upd(int i,bool t){
int u=i,k=0;
while(u){
if(t)
mn[u]=min(mn[u],dis[i][k]);
else
mn[u]=inf;
u=pac[u];
k++;
}
}
ll qr(int i){
int u=i,k=0;
ll res=inf;
while(u){
res=min(res,mn[u]+dis[i][k]);
//cout << mn[u] << " " << dis[i][k] << "\n\n";
u=pac[u];
k++;
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n-1;i++){
g[A[i]+1].push_back({B[i]+1,D[i]});
g[B[i]+1].push_back({A[i]+1,D[i]});
}
build(1,0);
pre(1);
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)
dp[i][j]=dp[dp[i][j-1]][j-1];
for(int i=1;i<=n;i++){
int u=i,k=0;
while(u){
dis[i][k]=dist(i,u);
//cout << dis[i][k] << " ";
k++;
u=pac[u];
}
//cout << "\n";
}
for(int i=1;i<=n;i++)
mn[i]=inf;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++)
upd(X[i]+1,1);
ll ans=inf;
for(int i=0;i<T;i++)
ans=min(ans,qr(Y[i]+1));
for(int i=0;i<S;i++)
upd(X[i]+1,0);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12464 KB |
Output is correct |
2 |
Correct |
239 ms |
31200 KB |
Output is correct |
3 |
Correct |
268 ms |
31192 KB |
Output is correct |
4 |
Correct |
272 ms |
31244 KB |
Output is correct |
5 |
Correct |
281 ms |
31520 KB |
Output is correct |
6 |
Correct |
184 ms |
31180 KB |
Output is correct |
7 |
Correct |
268 ms |
31320 KB |
Output is correct |
8 |
Correct |
262 ms |
31304 KB |
Output is correct |
9 |
Correct |
280 ms |
31584 KB |
Output is correct |
10 |
Correct |
178 ms |
31240 KB |
Output is correct |
11 |
Correct |
267 ms |
31244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12372 KB |
Output is correct |
2 |
Correct |
2186 ms |
200580 KB |
Output is correct |
3 |
Correct |
5295 ms |
202700 KB |
Output is correct |
4 |
Correct |
714 ms |
197836 KB |
Output is correct |
5 |
Correct |
7086 ms |
227988 KB |
Output is correct |
6 |
Correct |
5605 ms |
204784 KB |
Output is correct |
7 |
Correct |
981 ms |
68652 KB |
Output is correct |
8 |
Correct |
335 ms |
68572 KB |
Output is correct |
9 |
Correct |
1182 ms |
72676 KB |
Output is correct |
10 |
Correct |
991 ms |
70284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12464 KB |
Output is correct |
2 |
Correct |
239 ms |
31200 KB |
Output is correct |
3 |
Correct |
268 ms |
31192 KB |
Output is correct |
4 |
Correct |
272 ms |
31244 KB |
Output is correct |
5 |
Correct |
281 ms |
31520 KB |
Output is correct |
6 |
Correct |
184 ms |
31180 KB |
Output is correct |
7 |
Correct |
268 ms |
31320 KB |
Output is correct |
8 |
Correct |
262 ms |
31304 KB |
Output is correct |
9 |
Correct |
280 ms |
31584 KB |
Output is correct |
10 |
Correct |
178 ms |
31240 KB |
Output is correct |
11 |
Correct |
267 ms |
31244 KB |
Output is correct |
12 |
Correct |
7 ms |
12372 KB |
Output is correct |
13 |
Correct |
2186 ms |
200580 KB |
Output is correct |
14 |
Correct |
5295 ms |
202700 KB |
Output is correct |
15 |
Correct |
714 ms |
197836 KB |
Output is correct |
16 |
Correct |
7086 ms |
227988 KB |
Output is correct |
17 |
Correct |
5605 ms |
204784 KB |
Output is correct |
18 |
Correct |
981 ms |
68652 KB |
Output is correct |
19 |
Correct |
335 ms |
68572 KB |
Output is correct |
20 |
Correct |
1182 ms |
72676 KB |
Output is correct |
21 |
Correct |
991 ms |
70284 KB |
Output is correct |
22 |
Correct |
2521 ms |
207408 KB |
Output is correct |
23 |
Correct |
2563 ms |
210212 KB |
Output is correct |
24 |
Correct |
5805 ms |
210776 KB |
Output is correct |
25 |
Correct |
5848 ms |
214556 KB |
Output is correct |
26 |
Correct |
5849 ms |
210840 KB |
Output is correct |
27 |
Correct |
7944 ms |
231476 KB |
Output is correct |
28 |
Correct |
827 ms |
207932 KB |
Output is correct |
29 |
Correct |
5997 ms |
210592 KB |
Output is correct |
30 |
Correct |
5781 ms |
209944 KB |
Output is correct |
31 |
Correct |
6056 ms |
210540 KB |
Output is correct |
32 |
Correct |
1146 ms |
73692 KB |
Output is correct |
33 |
Correct |
342 ms |
68844 KB |
Output is correct |
34 |
Correct |
622 ms |
66116 KB |
Output is correct |
35 |
Correct |
674 ms |
66108 KB |
Output is correct |
36 |
Correct |
969 ms |
67032 KB |
Output is correct |
37 |
Correct |
950 ms |
66800 KB |
Output is correct |