Submission #1230994

#TimeUsernameProblemLanguageResultExecution timeMemory
1230994long290429Factories (JOI14_factories)C++20
0 / 100
849 ms589824 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=500005; int tin[maxn],tout[maxn]; int dep[maxn]; long long dtr[maxn]; vector<pair<int,long long>> adj[maxn]; int tt,lg; vector<vector<int>> up; 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]; } long long solve(int a[],int n,int b[],int m) { vector<int> c; for(int i=0;i<n;++i) { c.push_back(a[i]); } for(int i=0;i<m;++i) { c.push_back(b[i]); } sort(c.begin(),c.end(),[&](int u,int v) {return tin[u]<tin[v];}); for(int i =1;i<c.size();++i) { c.push_back(lca(c[i],c[i-1])); } sort(c.begin(),c.end(),[&](int u,int v) {return tin[u]<tin[v];}); c.erase(unique(c.begin(),c.end()),c.end()); int sz=c.size(); unordered_map<int,int> idx; idx.reserve(sz); for(int i=0;i<sz;++i) { idx[c[i]]=i; } vector<int> st; vector<vector<pair<int,int>>> vt(sz); for(int u:c){ int id=idx[u]; while(!st.empty()&&!(tin[c[st.back()]]<=tin[u]&&tout[u]<=tout[c[st.back()]])) { st.pop_back(); } if(!st.empty()) { int v=st.back(); int node=c[v]; int len=dtr[u]-dtr[node]; vt[v].push_back({id,len}); vt[id].push_back({v,len}); } st.push_back(id); } long long inf=LLONG_MAX/4,ans; ans=inf; 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; } 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); return ans; } void Init(int n,int u[],int v[],int w[]) { for(int i=0;i<n;++i) adj[i].clear(); for(int i=0;i<n-1;++i) { adj[u[i]].push_back({v[i],(long long)w[i]}); adj[v[i]].push_back({u[i],(long long)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[]) { return solve(x,s,y,t); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...