Submission #1199742

#TimeUsernameProblemLanguageResultExecution timeMemory
1199742mareksbRace (IOI11_race)C++20
31 / 100
182 ms114592 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int MAXN=200005; vector<pair<int,int>> mas[MAXN]; int ans=INT_MAX/4; int dist[1005][1005]; int n,k; queue<pair<int,int>> zl; bool visited[MAXN]; int dp[MAXN][105]; void dfs(int v,int p){ dp[v][0]=0; for(int i=1;i<=100;i++){ dp[v][i]=INT_MAX/4; } for(auto u:mas[v]){ if(u.first==p)continue; dfs(u.first,v); for(int i=0;i<=100;i++){ if(k-i-u.second<0)continue; ans=min(ans,dp[v][i]+1+dp[u.first][k-i-u.second]); //i //k-i-u.second } for(int i=1;i<=100;i++){ if(i-u.second<0)continue; dp[v][i]=min(dp[v][i],1+dp[u.first][i-u.second]); } } } int best_path(int N, int K, int H[][2], int L[]) { n=N; k=K; for(int i=0;i<N-1;i++){ int x=H[i][0]; int y=H[i][1]; mas[x].push_back({y,L[i]}); mas[y].push_back({x,L[i]}); } dfs(0,0); if(ans==INT_MAX/4){ return -1; } return ans; } /* 5 5 0 1 1 1 2 4 2 3 2 3 4 3 2 5 10 0 1 1 1 2 4 2 3 2 3 4 3 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...