제출 #805246

#제출 시각아이디문제언어결과실행 시간메모리
805246Kerim경주 (Race) (IOI11_race)C++17
31 / 100
244 ms116344 KiB
#include "race.h" #include "bits/stdc++.h" using namespace std; typedef pair<int, int> pii; const int N = 2e5+5; const int INF = 1e9; vector<pii> adj[N]; int K, answer; int dp[N][105]; void dfs(int nd, int pr){ dp[nd][0] = 0; for (int i = 1; i <= K; i++) dp[nd][i] = INF; for (auto [c, e]: adj[nd]){ if (c == pr) continue; dfs(c, nd); //update answer for (int w1 = 0; w1 + e <= K; w1++){ int w2 = K - e - w1; answer = min(answer, dp[nd][w1] + dp[c][w2]+1); } //update dp for (int p = 0; p+e <= K; p++) dp[nd][p+e] = min(dp[nd][p+e],dp[c][p]+1); } } int best_path(int n, int k, int H[][2], int L[]){ K = k; answer = INF; for (int i = 0; i < n - 1; i++){ int u = H[i][0], v = H[i][1], w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } if (k <= 100){ //subtask 1 and 3 dfs(1, -1); if (answer == INF) answer = -1; return answer; } return -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...