Submission #751876

#TimeUsernameProblemLanguageResultExecution timeMemory
751876aryan12Cyberland (APIO23_cyberland)C++17
97 / 100
3042 ms95424 KiB
#include "cyberland.h" #include <bits/stdc++.h> #include <vector> // #define int long long using namespace std; const int N = 1e5 + 1, K = 70; double dist[K][N]; vector<pair<int, double> > 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(int32_t n, int32_t m, int32_t k, int32_t h, vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, vector<int32_t> arr) { H = h; k = min(k, 69); 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[j][i] = 1e18; } } 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, pair<int, int> > > pq; for(int i = 0; i < n; i++) { // cout << "source[i] = " << source[i] << "\n"; if(source[i]) { pq.push({0, {i, 0}}); dist[0][i] = 0; } } while(!pq.empty()) { auto [dis, p] = pq.top(); auto [node, cur_k] = p; pq.pop(); dis = -dis; if(dist[cur_k][node] < dis || node == h) { continue; } for(auto [to, wt]: g[node]) { if(a[to] == 0) continue; if(dist[cur_k][to] > dist[cur_k][node] + wt) { dist[cur_k][to] = dist[cur_k][node] + wt; pq.push({-dist[cur_k][to], {to, cur_k}}); } if(a[to] == 1 || cur_k == k) continue; if(dist[cur_k + 1][to] > (dist[cur_k][node] + wt) / 2.0) { dist[cur_k + 1][to] = (dist[cur_k][node] + wt) / 2.0; pq.push({-dist[cur_k + 1][to], {to, cur_k + 1}}); } } } double ans = 1e18; // 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 = 0; i <= k; i++) { ans = min(ans, dist[i][h]); } 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...