제출 #297909

#제출 시각아이디문제언어결과실행 시간메모리
297909Hemimor경주 (Race) (IOI11_race)C++14
21 / 100
3061 ms22508 KiB
#include "race.h" #include <algorithm> #include <iostream> #include <iomanip> #include <numeric> #include <cassert> #include <vector> #include <cmath> #include <queue> #include <set> #include <map> #define syosu(x) fixed<<setprecision(x) using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> P; typedef pair<double,double> pdd; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<string> vs; typedef vector<P> vp; typedef vector<vp> vvp; typedef vector<pll> vpll; typedef pair<P,int> pip; typedef vector<pip> vip; const int inf=1<<30; const ll INF=1ll<<60; const double pi=acos(-1); const double eps=1e-8; const ll mod=1e9+7; const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; int res=inf; ll m; vi s,vis; vvp g; vp c[2]; int Cdfs(int v,int p){ s[v]=1; for(auto i:g[v]){ int u=i.first; if(!vis[u]&&u!=p) s[v]+=Cdfs(u,v); } return s[v]; } P Cdfs1(int v,int p,int S){ P q={inf,0}; int M=0,S_=S-1; for(auto i:g[v]){ int u=i.first; if(!vis[u]&&u!=p){ q=min(q,Cdfs1(u,v,S)); M=max(M,s[u]); S_-=s[u]; } } return min(q,{max(M,S_),v}); } int Cent(int v){ Cdfs(v,-1); return Cdfs1(v,-1,s[v]).second; } void dfs(int v,int par,int t,int len,vp &a){ if(t<=m) a.push_back({t,len}); if(t==m) res=min(res,len); for(auto p:g[v]){ int u=p.first; if(!vis[u]&&u!=par) dfs(u,v,min(inf,p.second+t),len+1,a); } } void Rec(int v){ v=Cent(v); vis[v]++; vvp b; int id=0; for(auto p:g[v]){ vp a; dfs(p.first,-1,p.second,1,a); b.push_back(a); for(auto q:a){ int t=q.first,len=q.second; if(c[0][t].second==id){ if(len<c[0][t].first) c[0][t]={len,id}; } else if(c[1][t].second==id){ if(len<c[1][t].first) c[1][t]={len,id}; if(c[0][t].first>c[1][t].first) swap(c[0][t],c[1][t]); } else if(len<c[0][t].first) c[1][t]=c[0][t],c[0][t]={len,id}; else if(len<c[1][t].first) c[1][t]={len,id}; } id++; } for(int i=0;i<(int)b.size();i++){ for(auto p:b[i]){ int t=m-p.first; if(c[0][t].second!=i) res=min(res,p.second+c[0][t].first); if(c[1][t].second!=i) res=min(res,p.second+c[1][t].first); } } for(int i=0;i<(int)b.size();i++) for(auto p:b[i]) c[0][p.first]=c[1][p.first]={inf,inf}; for(auto p:g[v]) { int u=p.first; if(!vis[u]) Rec(u); } } int best_path(int N, int K, int H[][2], int L[]){ m=K; s=vis=vi(N); g=vvp(N); c[0]=c[1]=vp(m+1,{inf,inf}); for(int i=0;i<N-1;i++){ int u=H[i][0],v=H[i][1]; g[u].push_back({v,L[i]}); g[v].push_back({u,L[i]}); } Rec(0); if(res==inf) res=-1; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...