Submission #836993

#TimeUsernameProblemLanguageResultExecution timeMemory
836993aZvezdaCyberland (APIO23_cyberland)C++17
0 / 100
3069 ms131900 KiB
#include "cyberland.h" #include <bits/stdc++.h> const int MAX_N = 1e5 + 10; const int MAX_K = 100; typedef long double ld; ld dist[MAX_N][MAX_K]; std::vector<std::pair<int, int> > g[MAX_N]; bool used[MAX_N]; void dfs(int x) { if(used[x]) { return; } used[x] = true; for(const auto &it : g[x]) { dfs(it.first); } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { for(int i = 0; i < M; i ++) { g[x[i]].push_back({y[i], c[i]}); g[y[i]].push_back({x[i], c[i]}); } dfs(0); std::priority_queue<std::pair<ld, std::pair<int, int> > > pq; K = std::min(K, MAX_K - 1); for(int i = 0; i < N; i ++) { for(int j = 0; j <= K; j ++) { dist[i][j] = 1e18; } } for(int i = 0; i < N; i ++) { if(arr[i] == 0 || i == 0) { dist[i][arr[i]] = 0; pq.push({0, {arr[i] != 0, i}}); } } while(!pq.empty()) { auto curr = pq.top(); pq.pop(); curr.first *= -1; if(curr.first > dist[curr.second.second][curr.second.first]) { continue; } for(const auto &it : g[curr.second.second]) { ld new_dist = curr.first + it.second; if(new_dist < dist[it.first][curr.second.first]) { dist[it.first][curr.second.first] = new_dist; pq.push({-new_dist, {curr.second.first, it.first}}); } if(arr[it.first] == 2 && curr.second.first < K) { new_dist /= 2; if(new_dist < dist[it.first][curr.second.first + 1]) { dist[it.first][curr.second.first + 1] = new_dist; pq.push({-new_dist, {curr.second.first + 1, it.first}}); } } } } ld ret = 1e18; for(int i = 0; i <= K; i ++) { ret = std::min(ret, dist[N - 1][i]); } return ret; }
#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...