제출 #997661

#제출 시각아이디문제언어결과실행 시간메모리
997661blacktulip경주 (Race) (IOI11_race)C++17
100 / 100
308 ms51800 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define endl "\n" #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((bas+son)/2) #define _ << " " << const int li = 1000005; vector<pair<int,int>> v[li]; int k; int sub[li],cnt[li],vis[li]; int cev=0,siz; inline void dfs(int node,int ata){ sub[node]=1; for(auto go:v[node]){ if(go.fi==ata)continue; if(vis[go.fi])continue; dfs(go.fi,node); sub[node]+=sub[go.fi]; } } inline int find_centroid(int node,int ata){ for(auto go:v[node]){ if(go.fi==ata)continue; if(vis[go.fi])continue; if(sub[go.fi]>=siz/2)return find_centroid(go.fi,node); } return node; } inline void calc(int node,int ata,int dep,int say){ if(dep>k)return ; cev=min(cev,cnt[k-dep]+say); //~ cout<<dep<<" () "<<say<<" :: "<<cnt[k-dep]<<" :: "<<cnt[dep]<<endl; for(auto go:v[node]){ if(go.fi==ata)continue; if(vis[go.fi])continue; calc(go.fi,node,dep+go.se,say+1); } } inline void increase(int node,int ata,int dep,int val){ if(dep>k)return ; if(val>=1000000000)cnt[dep]=1000000000; else cnt[dep]=min(1000000000,min(cnt[dep],val)); for(auto go:v[node]){ if(go.fi==ata)continue; if(vis[go.fi])continue; increase(go.fi,node,dep+go.se,val+1); } } inline void solve(int c){ dfs(c,-1); siz=sub[c]; c=find_centroid(c,-1);//artik c centroid //~ cout<<c<<" () "<<cev<<endl; vis[c]=1; cnt[0]=0; for(auto go:v[c]){ if(vis[go.fi])continue; calc(go.fi,c,go.se,1); increase(go.fi,c,go.se,1); } for(auto go:v[c]){ if(vis[go.fi])continue; increase(go.fi,c,go.se,1000000000); } for(auto go:v[c]){ if(vis[go.fi])continue; solve(go.fi); } } int best_path(int n, int K, int h[][2], int l[]){ k=K; for(int i=0;i<=k;i++)cnt[i]=1000000000; for(int i=0;i<n-1;i++){ v[h[i][0]].pb({h[i][1],l[i]}); v[h[i][1]].pb({h[i][0],l[i]}); } cev=1000000000; solve(0); if(cev==1000000000)cev=-1; return cev; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...