제출 #892444

#제출 시각아이디문제언어결과실행 시간메모리
892444d4xn사이버랜드 (APIO23_cyberland)C++17
44 / 100
35 ms13632 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; ll mn[N], dis[3][N]; vector<int> arr; vector<pair<int, ll>> adj[N]; void dijkstra(int x, int idx) { priority_queue<pair<ll, int>> pq; if (idx == 2) { for (int i = 0; i < n; 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()) { ll 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 a = dis[0][h]; ld ans = a; // solo 0 a = dis[2][h]; if (dis[2][h] != -1) ans = min(ans, a); // solo 2 for (int i = 0; i < n; i++) { if (arr[i] != 2 || dis[0][i] == -1 || dis[1][i] == -1) continue; ld div = 2; a = dis[0][i] / div; ld b = dis[1][i]; ans = min(ans, a + b); if (mn[i] != -1) { int l = 1; int r = k-1; while (l < r) { ld mid = (l+r)/2; ld val1 = a / (div*mid) + mn[i]*(mid-1) / div; ld val2 = a / (div*(mid+1)) + mn[i]*(mid) / div; if (val1 < val2) r = mid; else l = mid+1; } ld nwA = a / (div*l) + mn[i]*(l-1) / div; ans = min(ans, nwA + b); } } // 0 y 2 for (int i = 0; i < n; i++) { if (arr[i] != 2 || dis[0][i] == -1 || dis[1][i] == -1 || dis[2][i] == -1) continue; ld div = 2; a = dis[2][i] / div; ld b = dis[1][i]; ans = min(ans, a + b); if (mn[i] != -1) { int l = 1; int r = k-1; while (l < r) { ld mid = (l+r)/2; ld val1 = a / (div*mid) + mn[i]*(mid-1) / div; ld val2 = a / (div*(mid+1)) + mn[i]*(mid) / div; if (val1 < val2) r = mid; else l = mid+1; } ld nwA = a / (div*l) + mn[i]*(l-1) / div; ans = min(ans, nwA + b); } } 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...