Submission #951592

#TimeUsernameProblemLanguageResultExecution timeMemory
951592noyancanturkFactories (JOI14_factories)C++17
100 / 100
3657 ms222744 KiB
#include "factories.h" #pragma GCC optimize("O3,unroll-loops") #include "bits/stdc++.h" using namespace std; #define pb push_back const int lim=5e5+100; const int64_t inf=lim*1e9; using pii=pair<int,int64_t>; vector<pii>v[lim]; bool vis[lim]; int tot,cent,layer,sz[lim]; int onlayer[lim],centpar[20][lim]; int64_t dist[20][lim]; inline int sbs(int node,int par){ sz[node]=1; for(pii p:v[node]){ if(!vis[p.first]&&(p.first^par)){ sz[node]+=sbs(p.first,node); } } return sz[node]; } inline int findcent(int node,int par){ for(pii p:v[node]){ if(!vis[p.first]&&(p.first^par)&&tot<2*sz[p.first]){ return findcent(p.first,node); } } return node; } inline void distdfs(int node,int par){ centpar[layer][node]=cent; for(pii p:v[node]){ if(!vis[p.first]&&(p.first^par)){ dist[layer][p.first]=dist[layer][node]+p.second; distdfs(p.first,node); } } } inline void decomp(int node,int dep=0){ layer=dep; tot=sbs(node,-1); onlayer[cent=findcent(node,-1)]=dep; vis[cent]=1; dist[layer][cent]=0; distdfs(cent,-1); for(pii p:v[cent]){ if(!vis[p.first]){ decomp(p.first,dep+1); } } } int64_t curvals[lim]; 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]}); } for(int i=0;i<N;i++){ curvals[i]=inf; } decomp(0); } long long Query(int S, int X[], int T, int Y[]) { for(int i=0;i<S;i++){ for(int j=onlayer[X[i]];0<=j;j--){ curvals[centpar[j][X[i]]]=min(curvals[centpar[j][X[i]]],dist[j][X[i]]); } } int64_t ans=inf; for(int i=0;i<T;i++){ for(int j=onlayer[Y[i]];0<=j;j--){ ans=min(ans,curvals[centpar[j][Y[i]]]+dist[j][Y[i]]); } } for(int i=0;i<S;i++){ for(int j=onlayer[X[i]];0<=j;j--){ curvals[centpar[j][X[i]]]=inf; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...