Submission #1067485

#TimeUsernameProblemLanguageResultExecution timeMemory
1067485lovrotCyberland (APIO23_cyberland)C++17
8 / 100
351 ms44884 KiB
#include "cyberland.h" #include <vector> #include <algorithm> #include <set> #include <cstring> #define debug(...) fprintf(stderr, __VA_ARGS__) #define X first #define Y second #define PB push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int P = 60; const int N = 1e5 + 10; const double OO = 1e18; const double TSH = 1e-9; int k, n, h; vector<pii> g[N]; char con[N], bio[N][P], type[N]; double dp[N][P], ans; set<pair<double, pii>> s; void check(int u) { if(con[u]) { return; } con[u] = 1; if(u == h) { return; } for(pii e : g[u]) { check(e.X); } } void dijkstra() { for(int i = 0; i < n; ++i) { for(int j = 0; j < P; ++j) { dp[i][j] = OO; bio[i][j] = 0; } } dp[h][0] = 0; s.insert({dp[h][0], {h, 0}}); for(; !s.empty(); ) { int u = s.begin()->Y.X; int p = s.begin()->Y.Y; s.erase(s.begin()); if(bio[u][p] || type[u] == 0) { ans = min(ans, dp[u][p]); } bio[u][p] = 1; for(pii e : g[u]) { int v = e.X, w = e.Y, pp = type[v] == 2 ? min(p + 1, P - 1) : p; if(!bio[v][pp] && abs(dp[v][pp] - dp[u][p] - (double) w / (1LL << p)) > TSH) { dp[v][pp] = dp[u][p] + (double) w / (1LL << p); s.insert({dp[v][pp], {v, pp}}); } } } } double solve(int nn, int m, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { n = nn; k = min(kk, P); h = hh; for(int i = 0; i < n; ++i) { con[i] = 0; g[i].clear(); } for(int i = 0; i < m; ++i) { g[x[i]].PB({y[i], c[i]}); g[y[i]].PB({x[i], c[i]}); } for(int i = 0; i < n; ++i) { type[i] = arr[i]; } type[0] = 0; check(0); if(!con[h]) { return -1; } ans = OO; dijkstra(); 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...