제출 #874617

#제출 시각아이디문제언어결과실행 시간메모리
874617StickfishCyberland (APIO23_cyberland)C++17
97 / 100
3043 ms13732 KiB
#include "cyberland.h" #include <cmath> #include <vector> #include <cassert> #include <algorithm> #include <set> #include <bitset> using namespace std; const int MAXN = 1e5 + 123; const double INF = 1e18 + 177013; vector<pair<int, int>> edg[MAXN]; bitset<MAXN> used; void dfs_connect(int v, int H) { if (used[v]) return; used[v] = 1; if (v == H) return; for (auto [u, d] : edg[v]) { dfs_connect(u, H); } } void initialize(int N, int M, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { for (int i = 0; i < N; ++i) { edg[i].clear(); } used = 0; for (int i = 0; i < M; ++i) { edg[x[i]].push_back({y[i], c[i]}); edg[y[i]].push_back({x[i], c[i]}); } } vector<double> bfs(int N, const vector<pair<double, int>>& inits, double mod) { vector<double> depth(N, INF); set<pair<double, int>> rdepth; used = 0; for (const auto &[d, v] : inits) { depth[v] = d; rdepth.insert({d, v}); } while (rdepth.size()) { const auto [d, v] = *rdepth.begin(); rdepth.erase(rdepth.begin()); for (auto [u, len] : edg[v]) { if (d + len * mod < depth[u]) { rdepth.erase({depth[u], u}); depth[u] = d + len * mod; rdepth.insert({depth[u], u}); } } } return depth; } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { initialize(N, M, x, y, c, arr); dfs_connect(0, H); if (!used[H]) return -1; double __end_mod = 1; if (arr[H] == 0) return 0; if (arr[H] == 2 && K > 0) { arr[H] = 1; --K; __end_mod = 0.5; } bitset<MAXN> start; for (int i = 0; i < N; ++i) { start[i] = used[i] & (i == 0 || arr[i] == 0); } bitset<MAXN> div2; for (int i = 0; i < N; ++i) { div2[i] = arr[i] == 2 && used[i]; } //K = min({K, 200}); vector<double> depth; double ans = INF; depth = bfs(N, {{0, H}}, 1); for (int i = start._Find_first(); i < N; i = start._Find_next(i)) ans = min(ans, depth[i]); for (auto [u, d] : edg[H]) { edg[u].erase(find(edg[u].begin(), edg[u].end(), pair<int, int>(H, d))); } for (int ki = 1; ki <= K; ++ki) { vector<pair<double, int>> pts; for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) { pts.push_back({depth[i], i}); } double mod = pow(0.5, ki); depth = bfs(N, pts, mod); for (int i = start._Find_first(); i < N; i = start._Find_next(i)) ans = min(ans, depth[i]); vector<double> ndepth(N, INF); for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) { for (auto [u, d] : edg[i]) ndepth[i] = min(ndepth[i], depth[u] + d * mod); } for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) { depth[i] = ndepth[i]; } } return ans * __end_mod; }
#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...