Submission #756864

#TimeUsernameProblemLanguageResultExecution timeMemory
756864DarkMatterCyberland (APIO23_cyberland)C++17
78 / 100
1189 ms24048 KiB
#include "cyberland.h" /* * In the name of GOD */ #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; #define F first #define S second #define mk make_pair const ll N = 2e5 + 10, INF = 2e18 + 10; vector <pair <int, ll>> g[N]; ld dis[N], od[N], x[N]; int n, h; bool vis[N]; vector <int> ww; void dijkstra() { priority_queue <pair <ld, int>> q; for (int s = 0; s < n; s++) q.push(make_pair((ld)-1.0 * dis[s], s)); while (!q.empty()) { pair <ld, int> p = (q.top()); int x = p.S; q.pop(); if (dis[x] != -1 * p.F || x == h) continue; ld d = dis[x]; for (auto [y, w] : g[x]) { if (dis[y] <= d + w) { continue; } dis[y] = d + w; q.push(make_pair(-1 * dis[y], y)); } } } void dfs(int v) { vis[v] = true; for (auto [u, w] : g[v]) { if (!vis[u]) dfs(u); } } void dfs2(int v) { vis[v] = true; ww.push_back(v); for (auto [u, w] : g[v]) { if (!vis[u] && u != h) dfs2(u); } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { K = min(K, 70); n = N; h = H; for (int i = 0; i <= n; i++) g[i].clear(), vis[i] = false; for (int i = 0; i < M; i++) { g[x[i]].push_back(mk(y[i], c[i])); g[y[i]].push_back(mk(x[i], c[i])); } dfs(0); if (!vis[H]) { for (int i = 0; i <= n; i++) g[i].clear(), vis[i] = false; return -1; } for (int i = 0; i < n; i++) { dis[i] = INF; } for (int i = 0; i <= n; i++) vis[i] = false; ww.clear(); dfs2(0); for (int i : ww) { if (i == 0 || arr[i] == 0) dis[i] = 0; } ld mn = INF; for (int i = 0; i <= K; i++) { dijkstra(); mn = min(mn, dis[H]); dis[H] = INF; for (int i = 0; i < n; i++) od[i] = dis[i]; for (int i = 0; i < n; i++) { if (arr[i] == 2) { ld mnn = INF; for (auto [j, w] : g[i]) { mnn = min(mnn, od[j] + w); } dis[i] = min(dis[i], (mnn) / (ld)2); } } } for (int i = 0; i <= n; i++) g[i].clear(), vis[i] = false; return mn; }
#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...