Submission #1217433

#TimeUsernameProblemLanguageResultExecution timeMemory
1217433countlessRace (IOI11_race)C++20
0 / 100
0 ms320 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}); bool found = false; while (!pq.empty()) { auto [dist, count, u] = pq.front(); pq.pop(); vis[u] = true; for (auto &[v, w] : adj[u]) { if (!vis[v] and dist + w <= k) { if (dist + w == k) { best = count; found = true; break; } pq.push({dist + w, count + 1, v}); } } if (found) break; } } 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...