Submission #974214

#TimeUsernameProblemLanguageResultExecution timeMemory
974214PanndaCyberland (APIO23_cyberland)C++17
40 / 100
216 ms21212 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; double solve(int n, int m, int k, int t, vector<int> U, vector<int> V, vector<int> W, vector<int> type) { k = min(k, 30); vector<vector<array<int, 2>>> adj(n); for (int i = 0; i < n - 1; i++) { auto [u, v, w] = array<int, 3>{U[i], V[i], W[i]}; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } constexpr double INF = 1e18; constexpr double EPS = 1e-9; auto equal = [](double x, double y) -> bool { return abs(x - y) < EPS; }; vector<vector<double>> dist(n, vector<double>(k + 1, INF)); dist[t][0] = 0; priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<>> pq; pq.push(make_pair(dist[t][0], make_pair(0, t))); while (!pq.empty()) { auto [d, cu] = pq.top(); auto [c, u] = cu; pq.pop(); if (!equal(dist[u][c], d)) continue; for (auto [v, ww] : adj[u]) { if (v == t) continue; double w = ww; w /= (1 << c); if (d + w + EPS < dist[v][c]) { dist[v][c] = d + w; pq.push(make_pair(dist[v][c], make_pair(c, v))); } if (type[v] == 2 && c + 1 <= k) { c++; if (d + w + EPS < dist[v][c]) { dist[v][c] = d + w; pq.push(make_pair(dist[v][c], make_pair(c, v))); } c--; } } } type[0] = 0; vector<bool> reachable(n, false); queue<int> que; reachable[0] = true; que.push(0); while (!que.empty()) { int u = que.front(); que.pop(); for (auto [v, w] : adj[u]) { if (v == t) continue; if (!reachable[v]) { reachable[v] = true; que.push(v); } } } double ans = INF; for (int u = 0; u < n; u++) { if (reachable[u] && type[u] == 0) { double val = *min_element(dist[u].begin(), dist[u].end()); ans = min(ans, val); } } if (equal(ans, INF)) { return -1; } else { return ans; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...