#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define fs first
#define sc second
#define rng(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) rng(i,0,n)
#define vec vector
#define pb push_back
template<typename T>
void chmax(T &a,T b){a=max(a,b);}
template<typename T>
void chmin(T &a,T b){a=min(a,b);}
constexpr ll inf=1e17;
int n;
ll dpt[600000],dpt2[600000];
int pa[600000][20];
vec<bool>dead;
int root;
vec<int>tree[600000];
int par[600000];
vec<H>e[600000];
ll lca(int x,int y){
if(dpt2[x]<dpt2[y]) swap(x,y);
ll ret=0;
rep(i,20)if((1<<i)&(dpt2[x]-dpt2[y])){
ret+=dpt[x]-dpt[pa[x][i]];
x=pa[x][i];
}
for(int i=19;i>=0;i--){
if(pa[x][i]!=pa[y][i]){
ret+=dpt[x]-dpt[pa[x][i]];
ret+=dpt[y]-dpt[pa[y][i]];
x=pa[x][i];y=pa[y][i];
}
}
if(x!=y){
ret+=dpt[x]-dpt[pa[x][0]];
ret+=dpt[y]-dpt[pa[y][0]];
}
return ret;
}
int octr(int x){
static int sz[600000];
auto rec=[&](int pos,int p, auto& rec)->void{
sz[pos]=1;
for(auto g:e[pos]){
if(g.fs==p||dead[g.fs]) continue;
rec(g.fs,pos,rec);
sz[pos]+=sz[g.fs];
}
};
rec(x,-1,rec);
int N=sz[x];
auto dfs=[&](int pos,int p,auto& dfs)->int{
for(auto g:e[pos]){
if(g.fs==p||dead[g.fs]) continue;
if(sz[g.fs]>N/2) return dfs(g.fs,pos,dfs);
}
return pos;
};
return dfs(x,-1,dfs);
}
int build(int x){
int c=octr(x);
dead[c]=1;
if(root==-1) root=c;
for(auto g:e[c]){
if(dead[g.fs])continue;
int k=build(g.fs);
tree[c].pb(k);
par[k]=c;
}
return c;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
rep(i,n-1){
e[A[i]].pb(H{B[i],D[i]});
e[B[i]].pb(H{A[i],D[i]});
}
auto dfs=[&](int x,int p,ll d,int d2,auto& dfs)->void{
dpt[x]=d,pa[x][0]=p,dpt2[x]=d2;
for(auto g:e[x]){
if(g.fs==p) continue;
dfs(g.fs, x, d+g.sc,d2+1, dfs);
}
};
dfs(0,-1,0,0,dfs);
rep(i,n)rng(j,1,20) pa[i][j]=-1;
rep(j,19)rep(i,n){
if(pa[i][j]==-1) pa[i][j+1]=-1;
else pa[i][j+1]=pa[pa[i][j]][j];
}
root=-1;
dead.assign(n,false);
build(0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans=inf;
unordered_map<int, ll>mp;
rep(i,S){
int t=X[i]; mp[t]=0;
do{
t=par[t];
if(mp.find(t)==mp.end()) mp[t]=lca(t,X[i]);
else chmin(mp[t],lca(t,X[i]));
}while(t!=root);
}
rep(i,T){
int t=Y[i];
if(mp.find(t)!=mp.end()) chmin(ans,mp[t]);
do{
t=par[t];
if(mp.find(t)!=mp.end()) chmin(ans,lca(Y[i],t)+mp[t]);
}while(t!=root);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
29036 KB |
Output is correct |
2 |
Correct |
1980 ms |
37612 KB |
Output is correct |
3 |
Correct |
3284 ms |
37868 KB |
Output is correct |
4 |
Correct |
2481 ms |
37836 KB |
Output is correct |
5 |
Correct |
4204 ms |
38144 KB |
Output is correct |
6 |
Correct |
608 ms |
37484 KB |
Output is correct |
7 |
Correct |
3266 ms |
37612 KB |
Output is correct |
8 |
Correct |
3300 ms |
37644 KB |
Output is correct |
9 |
Correct |
4206 ms |
38252 KB |
Output is correct |
10 |
Correct |
605 ms |
37612 KB |
Output is correct |
11 |
Correct |
3253 ms |
38000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
28780 KB |
Output is correct |
2 |
Correct |
4867 ms |
125296 KB |
Output is correct |
3 |
Execution timed out |
8073 ms |
129292 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
29036 KB |
Output is correct |
2 |
Correct |
1980 ms |
37612 KB |
Output is correct |
3 |
Correct |
3284 ms |
37868 KB |
Output is correct |
4 |
Correct |
2481 ms |
37836 KB |
Output is correct |
5 |
Correct |
4204 ms |
38144 KB |
Output is correct |
6 |
Correct |
608 ms |
37484 KB |
Output is correct |
7 |
Correct |
3266 ms |
37612 KB |
Output is correct |
8 |
Correct |
3300 ms |
37644 KB |
Output is correct |
9 |
Correct |
4206 ms |
38252 KB |
Output is correct |
10 |
Correct |
605 ms |
37612 KB |
Output is correct |
11 |
Correct |
3253 ms |
38000 KB |
Output is correct |
12 |
Correct |
25 ms |
28780 KB |
Output is correct |
13 |
Correct |
4867 ms |
125296 KB |
Output is correct |
14 |
Execution timed out |
8073 ms |
129292 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |