제출 #151764

#제출 시각아이디문제언어결과실행 시간메모리
151764Kamisama경주 (Race) (IOI11_race)C++14
0 / 100
11 ms9848 KiB
#include <iostream> #include <cstdio> #include <iomanip> #include <chrono> #include <map> #include <vector> #include <functional> #include "race.h" #define Kami #define taskname "TEST" using namespace std; const int maxn=2e5+7; struct Edges{ int x,y,w; }; int n,k; int f[maxn][20],dis[maxn],lv[maxn],par[maxn]; bool isCentroid[maxn]; vector<int> adj[maxn],cen_child[maxn]; Edges e[maxn]; inline int Find_Centroid(const int &root){ static vector<int> sz(n+1); function<void(int,int)> GetSize=[&](const int &u, const int &p){ sz[u]=1; for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(v!=p && !isCentroid[v]){ GetSize(v,u); sz[u]+=sz[v]; } } }; GetSize(root,-1); int nChild=sz[root]; function<int(int,int)> Dfs=[&](const int &u, const int &p){ for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(v!=p && !isCentroid[v] && sz[v]>nChild/2) return Dfs(v,u); } return u; }; return Dfs(root,-1); } inline void Centroid_Decomposition(){ function<void(int,int)> Dfs=[&](const int &u, const int &p){ int centroid=Find_Centroid(u); isCentroid[centroid]=true; par[centroid]=p; if(p!=-1) cen_child[p].push_back(centroid); for(int i: adj[centroid]){ int v=e[i].x+e[i].y-centroid; if(!isCentroid[v]) Dfs(v,centroid); } isCentroid[centroid]=false; }; Dfs(1,-1); } inline void LCA_Prep(const int &u, const int &p){ f[u][0]=p; for(int i=1;i<20;i++){ int v=f[u][i-1]; if(v!=-1) f[u][i]=f[v][i-1]; else f[u][i]=-1; } for(int i: adj[u]){ int v=e[i].x+e[i].y-u; if(v==p) continue; dis[v]=dis[u]+e[i].w; lv[v]=lv[u]+1; LCA_Prep(v,u); } } inline int Jump(int u, int k){ for(int cur=0;k;k>>=1){ if(k&1) u=f[u][cur]; cur++; } return u; } inline int Lca(int u, int v){ if(lv[u]>lv[v]) swap(u,v); v=Jump(v,lv[v]-lv[u]); if(u==v) return u; for(int i=19;i>=0;i--) if(f[u][i]!=f[v][i]){ u=f[u][i]; v=f[v][i]; } return f[u][0]; } inline int Distance(const int &u, const int &v){ return dis[u]+dis[v]-2*dis[Lca(u,v)]; } inline int NumEdges(const int &u, const int &v){ return lv[u]+lv[v]-2*lv[Lca(u,v)]; } inline int Solve(){ int res=1e9+7; for(int root=1;root<=n;root++){ map<int,int> dp; function<void(int,int,int)> Dfs=[&](const int &u, const int &D, const int &E){ if(dp.find(D)==dp.end()) dp.insert(make_pair(D,E)); else dp.insert(make_pair(D,min(dp[D],E))); if(dp.find(k-D)!=dp.end()) res=min(res,E+dp[k-D]); for(int v: cen_child[u]) Dfs(v,D+Distance(u,v),E+NumEdges(u,v)); }; Dfs(root,0,0); } if(res!=1e9+7) return res; return -1; } int best_path(int N, int K, int H[][2], int L[]){ n=N; k=K; for(int i=0;i<N;i++){ e[i]={H[i][0]+1,H[i][1]+1,L[i]}; adj[e[i].x].push_back(i); adj[e[i].y].push_back(i); } Centroid_Decomposition(); LCA_Prep(1,-1); return Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...