Submission #972672

#TimeUsernameProblemLanguageResultExecution timeMemory
972672TheSahibCyberland (APIO23_cyberland)C++17
5 / 100
368 ms10708 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MXN = 1e5 + 5; const double oo = 1e15; int n, m, k, h; vector<pair<int, double>> adj[MXN]; int arr[MXN]; double dist[MXN], ndist[MXN]; priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq; vector<int> nodes; void dijk(int s, int F) { for(int i = 0; i < n; ++i){ ndist[i] = dist[i]; } for (int &x : nodes) ndist[x] = 0; if (F) { for (int i = 0; i < n; i++) { if (arr[i] != 2) continue; for (pair<int, double> &v : adj[i]) { if (v.first == h) continue; if (dist[v.first] == oo) continue; if (ndist[i] == -1) ndist[i] = (dist[v.first] + v.second) / 2; else ndist[i] = min(ndist[i], (dist[v.first] + v.second) / 2); } } } for (int i = 0; i < n; i++) { pq.push({ndist[i], i}); } while (!pq.empty()) { pair<double, int> f = pq.top(); pq.pop(); if (ndist[f.second] > f.first) continue; if (f.second == h) continue; for (pair<int, double> &v : adj[f.second]) { if (ndist[v.first] > f.first + v.second) { ndist[v.first] = f.first + v.second; pq.push({ndist[v.first], v.first}); } } } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR) { n = N, m = M, k = K, h = H; k = min(k, 70); for (int i = 0; i < n; i++) adj[i].clear(), arr[i] = ARR[i], dist[i] = -1; nodes.clear(); for (int i = 0; i < m; i++) { adj[x[i]].push_back({y[i], c[i]}); adj[y[i]].push_back({x[i], c[i]}); } vector<int> u(n, 0); queue<int> q; u[0] = 1, q.push(0); while (!q.empty()) { int f = q.front(); q.pop(); if (f == h) continue; for (pair<int, double> &v : adj[f]) { if (u[v.first]) continue; u[v.first] = 1, q.push(v.first); } } for (int i = 0; i < n; i++) { if (u[i] && (!i || arr[i] == 0)) { dist[i] = 0; nodes.push_back(i); } else dist[i] = oo; } double res = -1; for (int i = 0; i <= k; i++) { dijk(0, i); for (int j = 0; j < n; j++) { if (dist[i] == -1) dist[i] = ndist[i]; else if (ndist[i] != -1) dist[i] = min(dist[i], ndist[i]); } if (dist[h] != oo) { if (res == -1) res = dist[h]; else res = min(res, dist[h]); } } return res; }
#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...