제출 #804411

#제출 시각아이디문제언어결과실행 시간메모리
804411MadokaMagicaFan사이버랜드 (APIO23_cyberland)C++17
15 / 100
3065 ms10580 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; #define sz(v) ((int)(v).size()) #define pb push_back const int N = 1e5; vector<array<ll, 2>> adj[N]; bitset<N> v; ll mind1[N]; ll mind2[N]; ll sme[N]; ll inf = 1e18; double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { for (int i = 0; i < n; ++i) { sme[i] = inf; mind2[i] = inf; mind1[i] = 0; while (sz(adj[i])) adj[i].pop_back(); } v = 0; if (h == 0) return 0; for (int i = 0; i < m; ++i) { adj[x[i]].pb({y[i], c[i]}); if (y[i] != h) sme[x[i]] = min(sme[x[i]], (ll)c[i]); adj[y[i]].pb({x[i], c[i]}); if (x[i] != h) sme[y[i]] = min(sme[y[i]], (ll)c[i]); } priority_queue<array<ll, 2>> q; for (int i = 1; i < n; ++i) { if (arr[i] == 0) { q.push({0, i}); mind1[i] = 0; } else mind1[i] = inf; } q.push({0, 0}); while (sz(q)) { auto u = q.top(); q.pop(); if (v[u[1]]) continue; if (u[1] == h) continue; v[u[1]] = 1; for (auto x : adj[u[1]]) { if (mind1[u[1]]+ x[1] < mind1[x[0]]) { mind1[x[0]] = mind1[u[1]]+ x[1]; q.push({-mind1[x[0]], x[0]}); } } } if (mind1[h] > 1e17) return -1; long double ans = mind1[h]; while (sz(q)) q.pop(); mind2[h] = 0; q.push({0, h}); v = 0; while (sz(q)) { auto u = q.top(); q.pop(); if (v[u[1]]) continue; v[u[1]] = 1; for (auto x : adj[u[1]]) { if (mind2[u[1]]+ x[1] < mind2[x[0]]) { mind2[x[0]] = mind2[u[1]]+ x[1]; q.push({-mind2[x[0]], x[0]}); } } } for (int i = 1; i < n; ++i) { if (mind1[i] > 1e17) continue; if (arr[i] != 2) continue; long double v = mind1[i]; long double z = sme[i]; v = v / ((ld)2); int c = min(k-1, 100); if (sme[i] >= 1e17) c = 0; while (c && z * ((ld) 2) <= v) { v = v / ((ld) 2) + z; } z = mind2[i]; ans = min(ans, z + v); } 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...