| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 397940 | keta_tsimakuridze | 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 f first
#define s second
#define int long long
using namespace std;
const int NN=5e5+5,Inf=1e15;
int sz[NN],dist[NN][20],H[NN],mn[NN],par[NN],fix[NN];
vector<pair<int,int> >V[NN];
void get_sz(int u,int p){
sz[u] = 1;
for(int i=0;i<V[u].size();i++){
if(V[u][i].f!=p && !fix[V[u][i].f]) get_sz(V[u][i].f,u),sz[u]+=sz[V[u][i].f];
}
}
int find_centroid(int u,int p,int Sz){
for(int i=0;i<V[u].size();i++){
if(V[u][i].f==p || fix[V[u][i].f]) continue;
if(sz[V[u][i].f] > Sz/2) return find_centroid(V[u][i].f,u,Sz);
}
return u;
}
void dfs(int u,int p,int h){
for(int i=0;i<V[u].size();i++){
if(V[u][i].f==p || fix[V[u][i].f]) continue;
dist[V[u][i].f][h] = dist[u][h] + V[u][i].s;
dfs(V[u][i].f,u,h);
}
}
void centroid_decomp(int u,int p,int h){
get_sz(u,0);
int c = find_centroid(u,0,sz[u]);
par[c] = p;
H[c] = h;
mn[c] =Inf;
dfs(c,0,h);
fix[c] = 1;
for(int i=0;i<V[c].size();i++){
if(!fix[V[c][i].f]) centroid_decomp(V[c][i].f,c,h+1);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++){
V[A[i]].push_back({B[i],D[i]});
V[B[i]].push_back({A[i],D[i]});
}
centroid_decomp(1,0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> remove;
for(int i=0;i<S;i++){
int c = X[i];
while(c!=0){
if(mn[c] == Inf)remove.push_back(c);
mn[c] = min(mn[c],dist[X[i]][H[c]]);
c=par[c];
}
}
int ans = Inf;
for(int i =0;i<T;i++){
int c = Y[i];
while(c!=0){
ans = min(mn[c] + dist[Y[i]][H[c]],ans);
c=par[c];
}
}
for(int i=0;i<remove.size();i++){
mn[remove[i]]=Inf;
}
return ans;
}