Submission #753464

#TimeUsernameProblemLanguageResultExecution timeMemory
753464JomnoiCyberland (APIO23_cyberland)C++17
100 / 100
175 ms64596 KiB
#include <bits/stdc++.h> #include "cyberland.h" using namespace std; const int MAX_N = 1e5 + 5; const int MAX_K = 71; const long long INF = 1e18 + 7; vector <pair <int, int>> graph[MAX_N]; double power[MAX_K], dist[MAX_N][MAX_K]; bool visited[MAX_N]; double solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr) { K = min(K, 66); power[0] = 1.0; for (int i = 1; i <= K; i++) power[i] = power[i - 1] / 2.0; arr[0] = 0; for (int i = 0; i < N; i++) { graph[i].clear(); visited[i] = false; for (int k = 0; k <= K; k++) { dist[i][k] = INF; } } for (int i = 0; i < M; i++) { graph[x[i]].emplace_back(y[i], c[i]); graph[y[i]].emplace_back(x[i], c[i]); } queue <int> q; q.push(0); visited[0] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (auto [v, c] : graph[u]) { if (visited[v] == true or v == H) continue; visited[v] = true; q.push(v); } } priority_queue <tuple <double, int, int>> pq; pq.emplace(0, 0, H); dist[H][0] = 0; while (!pq.empty()) { auto [d, k, u] = pq.top(); pq.pop(); if (dist[u][k] < -d) continue; if (arr[u] == 0) return -d; for (auto [v, c] : graph[u]) { if (visited[v] == false) continue; if (dist[u][k] + power[k] * c < dist[v][k]) { dist[v][k] = dist[u][k] + power[k] * c; pq.emplace(-dist[v][k], k, v); } if (arr[v] == 2 and k < K and dist[u][k] + power[k] * c < dist[v][k + 1]) { dist[v][k + 1] = dist[u][k] + power[k] * c; pq.emplace(-dist[v][k + 1], k + 1, v); } } } return -1; }
#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...