Submission #1199752

#TimeUsernameProblemLanguageResultExecution timeMemory
1199752ricardsjansonsRace (IOI11_race)C++20
0 / 100
1 ms328 KiB
#include "race.h" #include <bits/stdc++.h> #define ll long long using namespace std; const int INF=1e9; vector<vector<int>>dp; vector<vector<pair<int,int>>>adj; int ans=INF; void dfs(int u=0,int p=-1){ vector<int>&res=dp[u]; int k=res.size()-1; res[0]=0; for(auto[v,l]:adj[u]){ if(v==p){ continue; } dfs(v,u); for(int i=0;i<=k&&k-i-l>=0;i++){ ans=min(ans,dp[v][i]+res[k-i-l]+1); } for(int i=l;i<=k;i++){ res[i]=min(res[i],dp[v][i-l]+1); } } } int best_path(int N, int K, int H[][2], int L[]) { adj.resize(N); dp=vector<vector<int>>(N,vector<int>(K+1,INF)); for(int i=0;i<N-1;i++){ auto[u,v]=H[i]; int l=L[i]; adj[u].push_back({v,l}); adj[v].push_back({u,l}); } dfs(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...