제출 #892401

#제출 시각아이디문제언어결과실행 시간메모리
892401d4xn사이버랜드 (APIO23_cyberland)C++17
15 / 100
3020 ms15696 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double const int N = 1e5+5; int n, h; ld mn[N], dis[3][N]; vector<int> arr; vector<pair<int, ld>> adj[N]; void dijkstra(int x, int idx) { priority_queue<pair<ld, int>> pq; if (idx == 2) { for (int i = 1; i < n-1; i++) { if (arr[i] || dis[0][i] == -1) continue; pq.push(make_pair(-0, i)); } } else { pq.push(make_pair(-0, x)); } while (!pq.empty()) { ld d = -pq.top().first; int y = pq.top().second; pq.pop(); if (dis[idx][y] != -1) continue; dis[idx][y] = d; if (idx != 1 && y == h) continue; for (auto& [z, d2] : adj[y]) { if (dis[idx][z] != -1) continue; pq.push(make_pair(-(d+d2), z)); } } } double solve(int N, int m, int k, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR) { n = N; h = H; arr.clear(); arr = ARR; for (int i = 0; i < n; i++) { adj[i].clear(); } for (int i = 0; i < m; i++) { adj[x[i]].push_back(make_pair(y[i], c[i])); adj[y[i]].push_back(make_pair(x[i], c[i])); } for (int i = 0; i < n; i++) { dis[0][i] = dis[1][i] = dis[2][i] = -1; mn[i] = -1; for (auto& [j, d] : adj[i]) { if (j == h) continue; if (mn[i] == -1) mn[i] = d; else mn[i] = min(mn[i], d); } } dijkstra(0, 0); dijkstra(h, 1); dijkstra(-1, 2); // nada ld ans = dis[0][h]; // solo 0 if (dis[2][h] != -1) ans = min(ans, dis[2][h]); // solo 2 for (int i = 1; i < n-1; i++) { if (!k || mn[i] == -1 || arr[i] != 2 || dis[0][i] == -1 || dis[1][i] == -1) continue; ld div = 2; ld x = dis[0][i] / div; int cnt = k-1; while (cnt > 0) { ld nwX = (x + mn[i]) / div; if (nwX > x) break; x = nwX; cnt--; } ans = min(ans, x + dis[1][i]); } // 0 y 2 for (int i = 1; i < n-1; i++) { if (!k || mn[i] == -1 || arr[i] != 2 || dis[0][i] == -1 || dis[1][i] == -1 || dis[2][i] == -1) continue; ld div = 2; ld x = dis[2][i] / div; int cnt = k-1; while (cnt > 0) { ld nwX = (x + mn[i]) / div; if (nwX > x) break; x = nwX; cnt--; } ans = min(ans, x + dis[1][i]); } 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...