Submission #1000834

#TimeUsernameProblemLanguageResultExecution timeMemory
1000834ALTAKEXERace (IOI11_race)C++17
31 / 100
352 ms262144 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; #define ff first #define ss second #define pii pair<int, int> int k, mn = INT_MAX; vector<vector<int>> dp; vector<vector<pii>> v, E; void dfs(int x, int p = - 1) { dp[x][0] = 0; for (auto [i, w] : E[x]) if (i != p) dfs(i, x); v.assign(k + 1, {}); for (auto [i, w] : E[x]) { if (i == p) continue; for (int j = w; j <= k; j++) { if (dp[i][j - w] == INT_MAX) continue; if ((int)v[j].size() < 2) v[j].push_back({dp[i][j - w] + 1, i}); else if (dp[i][j - w] + 1 < v[j][1].ff) v[j][1] = {dp[i][j - w] + 1, i}; if ((int)v[j].size() == 2 && v[j][0].ff > v[j][1].ff) swap(v[j][0], v[j][1]); dp[x][j] = min(dp[x][j], dp[i][j - w] + 1); } } if (!v[k].empty()) mn = min(mn, (int)v[k][0].ff); for (int i = 1; i < k; i++) { if (v[i].empty() || v[k - i].empty()) continue; if (v[i][0].ss != v[k - i][0].ss) mn = min(mn, v[i][0].ff + v[k - i][0].ff); else if (1 < (int)v[k - i].size()) mn = min(mn, v[i][0].ff + v[k - i][1].ff); } } int best_path(int N, int K, int H[][2], int L[]) { k = K; E.assign(N, {}); for (int i = 0; i < N - 1; i++) { E[H[i][0]].push_back({H[i][1], L[i]}); E[H[i][1]].push_back({H[i][0], L[i]}); } dp.assign(N, vector<int>(k + 1, INT_MAX)); dfs(0); return (mn == INT_MAX ? -1 : mn); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...