| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 852438 | epicci23 | Factories (JOI14_factories) | C++17 | 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"
using namespace std;
#define pb push_back
#define sz(x) ((int)(x).size())
const int N = 5e5 + 5;
const int LOG = 30;
const long long INF = 1e18;
vector<array<long long,2>> v[N];
int tin[N],tout[N];
long long depth[N];
int t=0;
int lift[N][LOG];
void dfs(int c,int p,long long d){
depth[c]=d;
tin[c]=t++;
tout[c]=tin[c];
lift[c][0]=p;
for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
for(auto x:v[c]){
if(x[0]==p) continue;
dfs(x[0],c,d+x[1]);
tout[c]=max(tout[c],tout[x[0]]);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++){
v[A[i]].pb({B[i],D[i]});
v[B[i]].pb({A[i],D[i]});
}
dfs(0,0,0);
}
bool check(int a,int b){
return tin[a] <= tin[b] && tin[b]<=tout[a];
}
int lca(int a,int b){
if(check(a,b)) return a;
for(int i=LOG-1;i>=0;i--){
if(!check(lift[a][i],b)) a=lift[a][i];
}
return lift[a][0];
}
long long Query(int S, int X[], int T, int Y[]){
long long ans=INF;
vector<pair<int,int>> cur;
for(int i=0;i<S;i++) cur.pb({X[i],0});
for(int i=0;i<T;i++) cur.pb({Y[i],1});
map<int,int> vis;
for(int i=0;i<sz(cur);i++) vis[cur[i].first]=1;
sort(cur.begin(),cur.end(),[&](pair<int,int> i,pair<int,int> j){
return tin[i.first] < tin[j.first];
});
vector<pair<int,int>> todo;
for(int i=1;i<sz(cur);i++){
if(!vis[lca(cur[i-1].first,cur[i].first)]){
todo.pb({lca(cur[i-1].first,cur[i].first),2});
vis[lca(cur[i-1].first,cur[i].first)]=1;
}
}
for(auto x:todo) cur.pb(x);
sort(cur.begin(),cur.end(),[&](pair<int,int> i,pair<int,int> j){
return tin[i.first] < tin[j.first];
});
cur.erase(unique(cur.begin(), cur.end()),cur.end());
vector<pair<int,long long>> g2[sz(cur) + 5];
array<long long,2> dp[sz(cur)+5];
fill(dp,dp+sz(cur)+5,make_pair(-1,-1));
stack<int> s;
s.push(0);
for(int i=1;i<(int)cur.size();i++){
int c = cur[i].first;
while(!check(cur[s.top()].first,c)) s.pop();
g2[s.top()].pb({i,depth[c]-depth[cur[s.top()].first]});
s.push(i);
}
for(int i=sz(cur)-1;i>=0;i--){
if(cur[i].second==0) dp[i][0]=depth[cur[i].first];
else if(cur[i].second==1) dp[i][1]=depth[cur[i].first];
for(auto x:g2[i]){
if(dp[x.first][0]!=-1) dp[i][0]=min(dp[i][0],dp[x.first][0]+x.second);
if(dp[x.first][1]!=-1) dp[i][1]=min(dp[i][1],dp[x.first][1]+x.second);
}
if(dp[i][0]!=-1 && dp[i][1]!=-1) ans=min(ans,dp[i][0]+dp[i][1]);
}
return ans;
}