| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 222898 | mhy908 | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
int n, q, siz[500010], d[500010], sparse[500010][30], centpar[500010];
vector<pil> link[500010];
bool ch[500010];
LL dep[500010];
void dfs(int num, int par){
siz[num]=1;
d[num]=d[par]+1;
sparse[num][0]=par;
for(auto i:link[num]){
if(i.F==par)continue;
dep[i.F]=dep[num]+i.S;
dfs(i.F, num);
siz[num]+=siz[i.F];
}
}
int lca(int x, int y){
if(d[x]>d[y])swap(x, y);
for(int i=20; i>=0; i--){
if(d[y]-d[x]>=(1<<i))y=sparse[y][i];
}
if(x==y)return x;
for(int i=20; i>=0; i--){
if(sparse[x][i]!=sparse[y][i]){
x=sparse[x][i];
y=sparse[y][i];
}
}
return sparse[x][0];
}
inline LL dist(int x, int y){return dep[x]+dep[y]-2*dep[lca(x, y)];}
int get_centroid(int num, int par, int sz){
bool flag=true;
for(auto i:link[num]){
if(ch[i.F])continue;
if(siz[i.F]>sz/2)flag=false;
}
if(flag)return num;
for(auto i:link[num]){
if(i.F==par||ch[i.F])continue;
int temp=siz[i.F];
siz[num]=sz-siz[i.F];
siz[i.F]=sz;
int ret=get_centroid(i.F, num, sz);
if(ret)return ret;
siz[num]=sz;
siz[i.F]=temp;
}
return 0;
}
void make_centroidtree(int num, int par){
int cen=get_centroid(num, 0, siz[num]);
ch[cen]=true;
centpar[cen]=par;
for(auto i:link[cen]){
if(ch[i.F])continue;
make_centroidtree(i.F, cen);
}
}
LL arr[500010];
vector<int> up[500010];
vector<LL> pardis[500010];
inline void update(int num){
for(int i=0; i<up[num].size(); i++)arr[up[num][i]]=min(arr[up[num][i]], pardis[num][i]);
}
inline LL query(int num){
LL ret=llinf;
for(int i=0; i<up[num].size(); i++)ret=min(ret, arr[up[num][i]]+pardis[num][i]);
return ret;
}
void cl(int num){
for(int i=0; i<up[num].size(); i++){
if(arr[up[num][i]]==llinf)break;
arr[up[num][i]]=llinf;
}
}
void Init(int N, int A[], int B[], int D[]){
n=N;
for(int i=0; i<n-1; i++){
int a=A[i];
int b=B[i]
LL c=(LL)D[i];
link[a+1].pb(mp(b+1, c));
link[b+1].pb(mp(a+1, c));
}
for(int i=1; i<=n; i++)arr[i]=llinf;
dfs(1, 0);
for(int j=1; j<=20; j++){
for(int i=1; i<=n; i++){
sparse[i][j]=sparse[sparse[i][j-1]][j-1];
}
}
make_centroidtree(1, 0);
for(int i=1; i<=n; i++){
int now=i;
while(now){
up[i].pb(now);
pardis[i].pb(dist(i, now));
now=centpar[now];
}
}
}
LL Query(int S, int X[], int T, int Y[]) {
for(int i=0; i<S; i++)update(X[i]+1);
LL ret=llinf;
for(int i=0; i<T; i++)ret=min(ret, query(Y[i]+1));
for(int i=0; i<S; i++)cl(X[i]+1);
return ret;
}