Submission #983250

#TimeUsernameProblemLanguageResultExecution timeMemory
983250c2zi6Cyberland (APIO23_cyberland)C++17
97 / 100
1980 ms2097152 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "cyberland.h" namespace DANDAX { typedef vector<vector<pair<int, ld>>> GRAPH; int n, m, k, h; GRAPH gp; VI col; typedef vector<ld> VD; typedef vector<VD> VVD; double sol(int N, int M, int K, int H, VI X, VI Y, VI C, VI ARR) { n = N, m = M, k = K, h = H; col = ARR; gp = GRAPH(n * (k+1)); rep(i, m) { int u = X[i]; int v = Y[i]; ld w = C[i]; gp[u].pb({v, w}); gp[v].pb({u, w}); replr(l, 0, k) { gp[u + n*l].pb({v + n*l, w}); gp[v + n*l].pb({u + n*l, w}); w /= 2; } } ld ans = 1e18; VD cur(n, 1e18); cur[0] = 0; for (int i = 0; i < 10; i++) { VD nxt(n, 1e18); rep(u, n) if (u != h) { for (auto[v, w] : gp[u]) { setmin(nxt[v], cur[u] + w); } } rep(u, n) if (col[u] == 2) if (nxt[u] != 1e18) nxt[u] /= 2; rep(u, n) if (col[u] == 0) if (nxt[u] != 1e18) nxt[u] = 0; cur = nxt; setmin(ans, cur[h]); } if (ans == 1e18) return -1; return ans; } } typedef vector<vector<pair<int, ld>>> GRAPH; int n, h; void dijkstra(GRAPH& gp, vector<ld>& dist, int s) { int n = gp.size(); priority_queue<pair<ld, int>> pq; dist = vector<ld>(n, 1e18); dist[s] = 0; pq.push({0, s}); VI vis(n); while (pq.size()) { int u = pq.top().ss; pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto[v, w] : gp[u]) { if (v%(::n) == h) continue; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({-dist[v], v}); } } } } int m, k; GRAPH gp; VI col; ld ans; VI vis; void dfs(int u, vector<ld>& dist) { if (u%n == h) return; if (col[u%n] == 0) setmin(ans, dist[u]); vis[u] = true; for (auto[v, w] : gp[u]) if (!vis[v]) dfs(v, dist); } double solve(int N, int M, int K, int H, VI X, VI Y, VI C, VI ARR) { n = N, m = M, k = K, h = H; col = ARR; gp = GRAPH(n * (k+1)); rep(i, m) { int u = X[i]; int v = Y[i]; ld w = C[i]; replr(l, 0, k) { gp[u + n*l].pb({v + n*l, w}); gp[v + n*l].pb({u + n*l, w}); w /= 2; } } rep(u, n) if (col[u] == 2) { ld dv = 2; replr(l, 0, k-1) { for (auto[v, w] : gp[u]) if (v < n) { gp[u + l*n].pb({v + n*(l+1), w/dv}); /* cout << "KOX: " << u + l*n << " " << v + n*(l+1) << " " << w/dv << endl; */ } dv *= 2; } } vector<ld> dist; dijkstra(gp, dist, h); /* for (ld x : dist) cout << x << " "; */ /* cout << endl; */ if (dist[0] == 1e18) return -1; col[0] = 0; vis = VI(gp.size()); ans = 1e18; dfs(0, dist); 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...