| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1317231 | h1drogen | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int NMAX = 500500;
vector<pair<int,int>> g[NMAX];
int dp[NMAX], tin[NMAX], tout[NMAX], up[21][NMAX];
int sz[NMAX], par[NMAX], best[NMAX], us[NMAX];
int tim;
void dfs(int v,int p,int sum){
tin[v]=tim++;
dp[v]=sum;
up[0][v]=p;
for(int i=1;i<=20;i++)
up[i][v]=up[i-1][up[i-1][v]];
for(auto [to,c]:g[v]){
if(to!=p)
dfs(to,v,sum+c);
}
tout[v]=tim;
}
void precalc(int v,int p){
sz[v]=1;
for(auto [to,c]:g[v]){
if(to!=p && !us[to]){
precalc(to,v);
sz[v]+=sz[to];
}
}
}
int get(int v,int p,int n){
for(auto [to,_]:g[v]){
if(sz[to]>n/2 && to!=p && !us[to])
return get(to,v,n);
}
return v;
}
bool check(int a,int b){
return tin[a]<=tin[b] && tout[b]<=tout[a];
}
int lca(int a,int b){
if(check(a,b)) return a;
if(check(b,a)) return b;
for(int i=20;i>=0;i--){
if(!check(up[i][a],b))
a=up[i][a];
}
return up[0][a];
}
int dist(int a,int b){
return dp[a]+dp[b]-2*dp[lca(a,b)];
}
void build(int v,int p){
precalc(v,-1);
int c=get(v,-1,sz[v]);
us[c]=1;
par[c]=p;
for(auto k:g[c]){
if(!us[k.first])
build(k.first,c);
}
}
void upd(int v,int x){
best[v]=min(best[v],dist(v,x));
if(par[v]<0) return;
upd(par[v],x);
}
void nulify(int v){
best[v]=INF;
if(par[v]<0) return;
nulify(par[v]);
}
int ans;
void res(int v,int x){
ans=min(ans,dist(v,x)+best[v]);
if(par[v]<0) return;
res(par[v],x);
}
// === Батч API ===
void Init(int N, int A[], int B[], int D[]) {
tim = 0;
for(int i=0;i<=N;i++){
g[i].clear();
dp[i]=0;
tin[i]=tout[i]=0;
par[i]=-1;
best[i]=INF;
us[i]=0;
sz[i]=0;
}
for(int i=0;i<N-1;i++){
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0,0,0);
build(0,-1);
for(int i=0;i<N;i++) best[i]=INF;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++)
upd(X[i], X[i]);
ans = INF;
for(int i=0;i<T;i++)
res(Y[i], Y[i]);
for(int i=0;i<S;i++)
nulify(X[i]);
return ans;
}