#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll dis[100001],n,i,j;
int jump[21][100001],dep[100001];
vector<pair<int,ll>> v[100001];
void dfs(int x,int y){
int i,nx,len;
jump[0][x]=y;
for(int i=0;i<v[x].size();i++){
nx=v[x][i].ff;
if(nx==y) continue;
len=v[x][i].ss;
dep[nx]=dep[x]+1;
dis[nx]=dis[x]+len;
dfs(nx,x);
}
}
int up(int x,int k){
for(i=0;i<=20;i++){
if(k&(1<<i)) x=jump[i][x];
}
return x;
}
int lca(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
y=up(y,dep[y]-dep[x]);
if(x==y) return x;
for(int i=20;i>0;i--){
if(jump[i][x]!=jump[i][y]){
x=jump[i][x];
y=jump[i][y];
}
}
return jump[0][x];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(i=0;i<N-1;i++){
v[A[i]].push_back({B[i],D[i]});
v[B[i]].push_back({A[i],D[i]});
}
dfs(0,0);
for(j=1;j<=20;j++){
for(i=0;i<N;i++){
jump[j][i]=jump[j-1][jump[j-1][i]];
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
ll res=1e18;
for(int i=0;i<S;i++){
for(int j=0;j<T;j++){
res=min(res,dis[X[i]]+dis[Y[j]]-2*dis[lca(X[i],Y[j])]);
}
}
return res;
}
Compilation message
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
factories.cpp:11:6: warning: unused variable 'i' [-Wunused-variable]
11 | int i,nx,len;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
29532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
29532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
