Submission #749251

#TimeUsernameProblemLanguageResultExecution timeMemory
749251dxz05Cyberland (APIO23_cyberland)C++17
97 / 100
3018 ms29116 KiB
#pragma GCC optimize("Ofast,O1,O2,O3,unroll-loops") #pragma GCC target("avx,avx2") #include "cyberland.h" #include <bits/stdc++.h> using namespace std; vector<vector<pair<int, double>>> g; vector<bool> used; vector<int> zeros; void dfs(int v, const vector<int> &arr){ used[v] = true; if (arr[v] == 0 || v == 0) zeros.push_back(v); for (auto [u, w] : g[v]){ if (!used[u]){ dfs(u, arr); } } } 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); g.clear(); g.resize(N); for (int i = 0; i < M; i++) { if (y[i] != H) g[x[i]].emplace_back(y[i], c[i]); if (x[i] != H) g[y[i]].emplace_back(x[i], c[i]); } zeros.clear(); used.assign(N, false); dfs(0, arr); const double INF = 2e15; const int T = 5; vector<vector<double>> dp(N, vector<double>(T, INF)); for (int v : zeros){ dp[v].assign(T, 0); } double ans = INF; for (int k = 0; k <= K; k++) { if (k > 0) { for (int i = 0; i < N; i++) { if (dp[i][(k + T - 1) % T] == INF) continue; dp[i][k % T] = min(dp[i][k % T], dp[i][(k + T - 1) % T]); if (arr[i] == 0) { dp[i][k % T] = 0; } } } priority_queue<pair<double, int>> pq; for (int i = 0; i < N; i++) { if (dp[i][k % T] != INF) pq.emplace(-dp[i][k % T], i); } vector<bool> processed(N, false); while (!pq.empty()) { int v = pq.top().second; pq.pop(); if (processed[v]) continue; processed[v] = true; for (auto [u, w]: g[v]) { dp[u][k % T] = min(dp[u][k % T], dp[v][k % T] + w); if (arr[u] == 0) { dp[u][k % T] = 0; } if (arr[u] == 2 && k < K) { dp[u][(k + 1) % T] = min(dp[u][(k + 1) % T], (dp[v][k % T] + w) / 2); } pq.emplace(-dp[u][k % T], u); } } for (int v = 0; v < N; v++){ dp[v][(k + T - 2) % T] = INF; } for (int v : zeros) dp[v][(k + T - 2) % T] = 0; for (auto [v, w]: g[H]) { if (dp[v][k % T] == INF) continue; if (arr[H] == 0) return 0; ans = min(ans, dp[v][k % T] + w); if (k < K && arr[H] == 2) { ans = min(ans, (dp[v][k % T] + w) / 2); } } } if (ans == INF) return -1; 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...