| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230879 | long290429 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int tin[maxn],tout[maxn];
int dep[maxn],dtr[maxn];
vector<pair<int,int>> adj[maxn];
int tt,lg;
vector<vector<int>> up;
long long inf=LLONG_MAX/4,ans;
void dfs(int u,int par) {
tin[u]=++tt;
up[u][0]=par;
for(int i=1;i<=lg;++i) {
if(up[u][i-1]!=-1) {
up[u][i]=up[up[u][i-1]][i-1];
}
else break;
}
for(pair<int,int> p:adj[u]) {
int v=p.first,w=p.second;
if(v==par) continue;
dep[v]=dep[u]+1;
dtr[v]=dtr[u]+w;
dfs(v,u);
}
tout[u]=tt;
}
int lca(int u,int v) {
if(dep[u]<dep[v]) swap(u,v);
int k=dep[u]-dep[v];
for(int i=0;k>0;++i) {
if(k&1) {
u=up[u][i];
}
k>>=1;
}
if(u==v) return u;
for(int i=lg;i>=0;--i) {
if(up[u][i]!=-1&&up[v][i]!=-1&&up[u][i]!=up[v][i]) {
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
void solve(int a[],int n,int b[],int m) {
vector<pair<int,int>> c(n+m);
for(int i=0;i<n+m;++i) {
if(i<n) c[i]=make_pair(tin[a[i]],a[i]);
else c[i]=make_pair(tin[b[i-n]],b[i-n]);
}
sort(c.begin(),c.end());
int sz=c.size();
for(int i=1;i<sz;++i) {
int anc=lca(c[i].second,c[i-1].second);
c.push_back({tin[anc],anc});
}
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
sz=c.size();
unordered_map<int,int> idx;
idx.reserve(sz);
for(int i=0;i<sz;++i) {
idx[c[i].second]=i;
}
vector<int> st;
vector<vector<pair<int,int>>> vt(sz);
for(pair<int,int> p:c){
int u=p.second;
int id=idx[u];
while(!st.empty()&&!(tin[c[st.back()].second]<=tin[u]&&tout[u]<=tout[c[st.back()].second])) {
st.pop_back();
}
if(!st.empty()) {
int v=st.back();
int node=c[v].second;
int len=dtr[u]-dtr[node];
vt[v].push_back({id,len});
vt[id].push_back({v,len});
}
st.push_back(id);
}
vector<long long> da(sz,inf),db(sz,inf);
for(int i=0;i<n;++i) {
da[idx[a[i]]]=0;
}
for(int i=0;i<m;++i) {
db[idx[b[i]]]=0;
}
ans=inf;
function<void(int,int)> dfs1=[&](int u,int par) {
for(pair<int,int> p:vt[u]) {
int v=p.first,w=p.second;
if(v==par) continue;
dfs1(v,u);
da[u]=min(da[u],da[v]+w);
db[u]=min(db[u],db[v]+w);
}
ans=min(ans,da[u]+db[u]);
};
dfs1(st[0],-1);
function<void(int,int)> dfs2=[&](int u,int par) {
for(pair<int,int> p:vt[u]) {
int v=p.first,w=p.second;
if(v==par) continue;
da[v]=min(da[v],da[u]+w);
db[v]=min(db[v],db[u]+w);
ans=min(ans,da[v]+db[v]);
dfs2(v,u);
}
};
dfs2(st[0],-1);
cout << ans << "\n";
}
void init(int n,int u[],int v[],int w[]) {
for(int i=0;i<n-1;++i) {
adj[u[i]].push_back({v[i],w[i]});
adj[v[i]].push_back({u[i],w[i]});
}
tt=0;
dep[0]=0;
dtr[0]=0;
lg=floor(log2(n));
up.assign(n,vector<int>(lg+1,-1));
dfs(0,-1);
}
long long query(int s,int x[],int t,int y[]) {
solve(s,x,t,y);
}