Submission #955222

#TimeUsernameProblemLanguageResultExecution timeMemory
955222Vanilla경주 (Race) (IOI11_race)C++17
100 / 100
436 ms83540 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; const int maxn=2e5+2; vector<pair<int,int>>ad[maxn]; map<int,int>mp[maxn]; int rs=1e9; void dfs(int u,int p,int k,int d,int h) { mp[u][d]=h; for(auto[v,c]:ad[u]) { if(v==p)continue; dfs(v,u,k,d+c,h+1); if(mp[v].size()>mp[u].size())swap(mp[u],mp[v]); for(auto[cost,node]:mp[v]){ int rem=k+2*d-cost; if (mp[u].count(rem)){ rs=min(rs,mp[u][rem]+node-2*h); } } for(auto[cost,node]:mp[v]){ if(!mp[u].count(cost))mp[u][cost]=node; mp[u][cost]=min(mp[u][cost],node); } } } int best_path(int n,int k,int h[][2],int l[]){ for(int i=0;i<n-1;i++){ ad[h[i][0]].push_back({h[i][1],l[i]}); ad[h[i][1]].push_back({h[i][0],l[i]}); } dfs(0,-1,k,0,0); return rs==(int)1e9?-1:rs; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...