| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286408 | Faisal_Saqib | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int KP=5e5+10,NP=1e6+10,lg=20;
int n,in[KP];
vector<pair<int,int>> ma[KP];
ll h[KP],mi[NP][lg];
vector<int> ord;
void dfs(int x,int p=-1)
{
in[x]=ord.size();
ord.push_back(x);
for(auto y:ma[x])
{
if(y.second!=p)
{
h[y.second]=h[x]+y.first;
dfs(y.second,x);
ord.push_back(x);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
ord.clear();
for(int i=0;i<=n;i++)h[i]=0,ma[i].clear();
for(int i=0;i<n-1;i++)
{
ma[A[i]].push_back({D[i],B[i]});
ma[B[i]].push_back({D[i],A[i]});
}
dfs(0);
// cout<<"ORD: ";
// for(auto x:ord)cout<<x<<' ';
// cout<<endl;
// cout<<"Hei: ";
for(int i=0;i<ord.size();i++)
{
mi[i][0]=h[ord[i]];
// cout<<h[ord[i]]<<' ';
}
// cout<<endl;
for(int j=1;j<lg;j++)
{
for(int i=0;i+(1<<j)-1<ord.size();i++)
{
mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
}
// cout<<ord.size()<<endl;
// ord.size() = 2*n-1
}
ll dist(int x,int y)
{
if(x>y)swap(x,y);
// [x,y]
int lp=__lg(y-x+1);
return min(mi[x][lp],mi[y-(1<<lp)+1][lp]);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans=1e18;
for(int i=0;i<S;i++)
{
int x=X[i];
for(int j=0;j<T;j++)
{
int y=Y[j];
ans=min(ans,h[x]+h[y]-2*dist(in[x],in[y]));
}
}
return ans;
}