Submission #972678

#TimeUsernameProblemLanguageResultExecution timeMemory
972678TheSahibCyberland (APIO23_cyberland)C++17
0 / 100
340 ms10708 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MXN = 1e5 + 5; 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] = -1; 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 (ndist[v.first] == -1) ndist[v.first] = (dist[i] + v.second) / 2; else ndist[v.first] = min(ndist[v.first], (dist[i] + v.second) / 2); } } } for (int i = 0; i < n; i++) { if (dist[i] != -1 && ndist[i] != -1) pq.push({min(dist[i], ndist[i]), i}); else if (ndist[i] != -1) pq.push({ndist[i], i}); else if (dist[i] != -1) pq.push({dist[i], i}); } while (!pq.empty()) { pair<double, int> f = pq.top(); pq.pop(); if (ndist[f.second] < f.first) continue; for (pair<int, double> &v : adj[f.second]) { if (ndist[v.first] == -1) { ndist[v.first] = f.first + v.second; pq.push({ndist[v.first], v.first}); } else 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]}); } adj[h].clear(); vector<int> u(n, 0); queue<int> q; u[0] = 1, q.push(0); while (!q.empty()) { int f = q.front(); q.pop(); 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] = -1; } 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] != -1) { 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...