Submission #1217376

#TimeUsernameProblemLanguageResultExecution timeMemory
1217376countlessRace (IOI11_race)C++20
21 / 100
3094 ms10492 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sp <<" "<< #define endl "\n" int best_path(int N, int K, int H[][2], int L[]) { ll k = K; vector<vector<pair<int, ll>>> adj(N); for (int i = 0; i < N - 1; i++) { auto [u, v] = H[i]; ll w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } vector<pair<ll, ll>> dist(N); auto dfs = [&](auto &&dfs, int u, int p = -1) -> void { for (auto &[v, w] : adj[u]) { if (v != p) { dist[v] = {dist[u].first + w, dist[u].second + 1}; dfs(dfs, v, u); } } }; ll best = LLONG_MAX; for (int i = 0; i < N; i++) { dist[i] = {0, 0}; dfs(dfs, i); for (int j = 0; j < N; j++) { if (dist[j].first == k) { best = min(best, dist[j].second); } } } if (best == LLONG_MAX) best = -1; return best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...