Submission #1217431

#TimeUsernameProblemLanguageResultExecution timeMemory
1217431countlessRace (IOI11_race)C++20
9 / 100
3090 ms9396 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}); } // [dist, count, at] using state = tuple<ll, ll, ll>; ll best = LLONG_MAX; for (int i = 0; i < N; i++) { queue<state> pq; vector<bool> vis(N, false); pq.push({0, 0, i}); while (!pq.empty()) { auto [dist, count, u] = pq.front(); pq.pop(); if (dist > k) break; if (dist == k) best = min(best, count); vis[u] = true; for (auto &[v, w] : adj[u]) { if (!vis[v]) { pq.push({dist + w, count + 1, v}); } } } } 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...