Submission #1243173

#TimeUsernameProblemLanguageResultExecution timeMemory
1243173hoangmc2009Factories (JOI14_factories)C++17
100 / 100
3614 ms162176 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; i64 n,q,dist[500009],mindist[500009]; int _t=0,tin[500009],tout[500009],par[20][500009]; vector<pair<int,i64>> adj[500009],bdj[500009]; void DFS(int u,int pu,i64 d) { tin[u]=++_t; dist[u]=d; par[0][u]=pu; for(auto& v:adj[u]) if(v.first!=pu) DFS(v.first,u,d+v.second); tout[u]=_t; } bool isA(int u,int v) {return tin[u]<=tin[v] and tout[v]<=tout[u];} int LCA(int u,int v) { if(isA(u,v)) return u; if(isA(v,u)) return v; for(int i=19;i>=0;--i) if(!isA(par[i][u],v)) u=par[i][u]; return par[0][u]; } //i64 dist2(int u,int v) {return dist[u]+dist[v]-2*dist[LCA(u,v)];} void Init(int N,int A[],int B[],int D[]) { n=N; for(int i=0;i<n-1;++i) { ++A[i]; ++B[i]; adj[A[i]].push_back({B[i],D[i]}); adj[B[i]].push_back({A[i],D[i]}); } DFS(1,0,0); par[0][1]=1; for(int i=1;i<20;++i) for(int j=1;j<=n;++j) par[i][j]=par[i-1][par[i-1][j]]; } i64 Query(int S,int X[],int T,int Y[]) { i64 res=9e18; vector<int> Z(S+T); for(int i=0;i<S;++i) Z[i]=++X[i]; for(int i=0;i<T;++i) Z[i+S]=++Y[i]; sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];}); for(int i=1;i<S+T;++i) Z.push_back(LCA(Z[i],Z[i-1])); sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];}); Z.resize(distance(Z.begin(),unique(Z.begin(),Z.end()))); stack<int> st; st.push(Z[0]); mindist[Z[0]]=3e18; for(int i=1;i<Z.size();++i) { while(!isA(st.top(),Z[i])) st.pop(); bdj[st.top()].push_back({Z[i],dist[Z[i]]-dist[st.top()]}); bdj[Z[i]].push_back({st.top(),dist[Z[i]]-dist[st.top()]}); st.push(Z[i]); mindist[Z[i]]=3e18; } priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> dij; for(int i=0;i<S;++i) { mindist[X[i]]=0; dij.push({0,X[i]}); } while(!dij.empty()) { pair<i64,int> u=dij.top(); dij.pop(); if(mindist[u.second]!=u.first) continue; for(auto& v:bdj[u.second]) { if(mindist[v.first]>u.first+v.second) { mindist[v.first]=u.first+v.second; dij.push({mindist[v.first],v.first}); } } } for(int i=0;i<T;++i) res=min(res,mindist[Y[i]]); for(int i=0;i<Z.size();++i) bdj[Z[i]].clear(); return res; } // No Raven here :((, cuz size limit exceeded
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...