Submission #805252

#TimeUsernameProblemLanguageResultExecution timeMemory
805252KerimRace (IOI11_race)C++17
43 / 100
248 ms113244 KiB
#include "race.h" #include "bits/stdc++.h" #define ll long long 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); } } void dfs1(int nd, int pr, int lvl, ll weight){ if (weight == K) answer = min(answer, lvl); if (weight >= K) return; for (auto [c, e]: adj[nd]){ if (c == pr) continue; dfs1(c, nd, lvl+1, weight+e); } } 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); else if(n <= 1000){ //subtask 2 for (int i = 0; i < n; i++) dfs1(i, -1, 0, 0); } if (answer == INF) answer = -1; return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...