Submission #751895

#TimeUsernameProblemLanguageResultExecution timeMemory
751895aryan12Cyberland (APIO23_cyberland)C++17
97 / 100
3069 ms93032 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; const int N = 1e5, K = 68; double dist[N][K]; vector<pair<int, int> > g[N]; bool vis[N], source[N]; int a[N], H; void dfs(int node) { vis[node] = true; if(a[node] == 0) { source[node] = true; } if(node == H) { return; } for(auto [to, wt]: g[node]) { if(!vis[to]) { dfs(to); } } } double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { H = h; k = min(k, 67); for(int i = 0; i <= n; i++) { source[i] = false; vis[i] = false; if(i != n) a[i] = arr[i]; g[i].clear(); for(int j = 0; j <= k; j++) { dist[i][j] = 1e14; } } for(int i = 0; i < m; i++) { g[x[i]].push_back({y[i], c[i]}); g[y[i]].push_back({x[i], c[i]}); } dfs(0); source[0] = true; if(!vis[H]) { return -1; } priority_queue<pair<double, int> > pq; for(int i = 0; i < n; i++) { // cout << "source[i] = " << source[i] << "\n"; if(source[i]) { pq.push({0, i}); dist[i][0] = 0; } } while(!pq.empty()) { auto [dis, p] = pq.top(); pq.pop(); int cur_k = p / 100000, node = p % 100000; dis = -dis; if(dist[node][cur_k] < dis || node == h) { continue; } for(auto [to, wt]: g[node]) { if(a[to] == 0) continue; double wt_d = wt; if(dist[to][cur_k] > dist[node][cur_k] + wt_d) { dist[to][cur_k] = dist[node][cur_k] + wt_d; pq.push({-dist[to][cur_k], to + 100000 * cur_k}); } if(a[to] == 1 || cur_k == k) continue; if(dist[to][cur_k + 1] > (dist[node][cur_k] + wt_d) / 2.0) { dist[to][cur_k + 1] = (dist[node][cur_k] + wt_d) / 2.0; pq.push({-dist[to][cur_k + 1], to + 100000 * (cur_k + 1)}); } } } double ans = dist[h][0]; // for(int i = 0; i < n; i++) // { // for(int j = 0; j <= k; j++) // { // cout << "dist[" << i << "][" << j << "] = " << dist[i][j] << "\n"; // } // } for(int i = 1; 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...