Submission #1000844

#TimeUsernameProblemLanguageResultExecution timeMemory
1000844ALTAKEXERace (IOI11_race)C++17
0 / 100
2 ms4696 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<pair<int, int>>> adj, x; vector<vector<int>> dp; int k, mn = INT_MAX; void dfs(int v, int p) { dp[v][0] = 0; for (auto [i, w] : adj[v]) if (i != p) dfs(i, v); x.assign(k + 1, {}); for (auto [i, w] : adj[v]) { if (i == p) continue; for (int j = w; j <= k; j++) { if (dp[i][j - w] == INT_MAX) continue; if ((int)x[j].size() < 2) x[j].push_back({dp[i][j - w] + 1, i}); else if (dp[i][j - w] + 1 < x[j][1].first) x[j][1] = {dp[i][j - w] + 1, i}; if ((int)x[j].size() == 2 && x[j][0].first > x[j][1].first) swap(x[j][0], x[j][1]); dp[v][j] = min(dp[v][j], dp[i][j - w] + 1); } } if (!x[k].empty()) mn = min(mn, (int)x[k][0].first); for (int i = 1; i < k; i++) { if (x[i].empty() || x[k - i].empty()) continue; if (x[i][0].second != x[k - i][0].second) mn = min(mn, x[i][0].first + x[k - i][0].first); else if (1 < (int)x[k - i].size()) mn = min(mn, x[i][0].first + x[k - i][1].first); } } int best_path(int N, int K, int H[][2], int L[]) { k = K; adj.assign(N, {}); for (int i = 0; i < N - 1; i++) { adj[H[i][0] + 1].push_back({H[i][1] + 1, L[i]}); adj[H[i][1] + 1].push_back({H[i][0] + 1, L[i]}); } dp.assign(N, vector<int>(k + 1, INT_MAX)); dfs(0, -1); if (mn == INT_MAX) return -1; else return 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...