Submission #979544

#TimeUsernameProblemLanguageResultExecution timeMemory
979544phoenix0423Cyberland (APIO23_cyberland)C++17
15 / 100
950 ms57756 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define pb push_back #define eb emplace_back #define f first #define s second #include "cyberland.h" const int maxn = 2e5 + 5; const double INF = 1e18; const double eps = 1e-9; vector<pll> adj[maxn]; int vis[maxn]; double dist[maxn][81]; struct info{ double d; int pos, l; info(){} info(double _d, int _pos, int _l) : d(_d), pos(_pos), l(_l){} bool operator < (const info& other) const{ return d < other.d; } bool operator > (const info& other) const{ return d > other.d; } }; priority_queue<info, vector<info>, greater<info>> q; 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, 80); for(int i = 0; i < n; i++) adj[i].clear(), vis[i] = 0; for(int i = 0; i < m; i++){ adj[x[i]].pb({y[i], c[i]}); adj[y[i]].pb({x[i], c[i]}); } for(int i = 1; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = INF; queue<int> nq; nq.push(0); vis[0] = 1; while(!nq.empty()){ int pos = nq.front(); nq.pop(); for(auto [x, w] : adj[pos]){ if(!vis[x]) vis[x] = 1, nq.push(x); } } arr[0] = 0; if(!vis[h]) return -1; for(int i = 0; i < n; i++){ if(arr[i] == 0 && vis[i]){ dist[i][0] = 0; q.push(info(0, i, 0)); } } while(!q.empty()){ auto [d, pos, l] = q.top(); q.pop(); if(dist[pos][l] < d || pos == h) continue; if(arr[pos] == 0) dist[pos][l] = d = 0; for(auto [x, w] : adj[pos]){ if(dist[x][l] > d + w){ dist[x][l] = d + w; q.push(info(dist[x][l], x, l)); } } if(arr[pos] == 2 && l < k){ d /= 2, l++; if(dist[pos][l] < d) continue; for(auto [x, w] : adj[pos]){ if(dist[x][l] > d + w){ dist[x][l] = d + w; q.push(info(dist[x][l], x, l)); } } } } double ans = INF; for(int i = 0; i <= k; i++) ans = min(ans, dist[h][i]); 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...