제출 #691568

#제출 시각아이디문제언어결과실행 시간메모리
691568zeroesandones경주 (Race) (IOI11_race)C++17
9 / 100
120 ms93472 KiB
#include "bits/stdc++.h" #include "race.h" using namespace std; using ll = long long; using vi = vector<ll>; using pi = pair<ll, ll>; const int mxN = 2e5 + 5; const ll inf = 1e15; ll dp[mxN][105]; vector<pi> adj[mxN]; void dfs(int x, int p) { fill(dp[x], dp[x] + 105, inf); dp[x][0] = 0; for(auto [y, w] : adj[x]) { if(y == p) continue; dfs(y, x); for(int j = w; j <= 100; ++j) { dp[x][j] = min(dp[x][j], dp[y][j - w] + 1); } } } int best_path(int N, int K, int H[][2], int L[]) { ll ans = inf; for(int i = 0; i < N - 1; ++i) { adj[H[i][0]].emplace_back(H[i][1], L[i]); adj[H[i][1]].emplace_back(H[i][0], L[i]); } dfs(0, -1); for(int i = 0; i < N; ++i) { ans = min(ans, dp[i][K]); } return (ans < inf ? ans : -1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...