Submission #973613

#TimeUsernameProblemLanguageResultExecution timeMemory
973613saayan007Cyberland (APIO23_cyberland)C++17
20 / 100
3049 ms527956 KiB
#include "bits/stdc++.h" #include "cyberland.h" using namespace std; const char nl = '\n'; #include <vector> struct UFDS{ int n; vector<int> lnk, sz; UFDS(int N) { n = N; lnk.resize(n); iota(lnk.begin(), lnk.end(), 0); sz.resize(n, 1); } int find(int a) { return (a == lnk[a] ? a : lnk[a] = find(lnk[a])); } bool same(int a, int b) { return (find(a) == find(b)); } void unite(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); lnk[b] = a; sz[a] += sz[b]; } }; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { K = min(K, 70); vector<pair<int, double>> adj[N]; UFDS uf(N); for(int i = 0; i < M; ++i) { adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); if(x[i] != H && y[i] != H) uf.unite(x[i], y[i]); } /* cout << N << " cities" << nl; */ /* cout << M << " edges" << nl; */ /* cout << H << " destination" << nl; */ /* for(int i = 0; i < M; ++i) { */ /* cout << i << " : "; */ /* for(auto u : adj[i]) { */ /* cout << "(" << u.first << ", " << u.second << ") "; */ /* } */ /* cout << nl; */ /* } */ double dist[N][K + 1]; for(int i = 0; i < N; ++i) { for(int j = 0; j <= K; ++j) { dist[i][j] = -1; } } priority_queue<pair<double, pair<int, int>>> pq; dist[0][0] = 0; pq.push({-dist[0][0], {0, 0}}); for(int i = 0; i < N; ++i) { if(uf.same(i, 0) && arr[i] == 0) { dist[i][0] = 0; pq.push({-dist[i][0], {0, i}}); } } while(!pq.empty()) { int a = pq.top().second.second; int st = -pq.top().second.first; double d = -pq.top().first; pq.pop(); if(dist[a][st] < d || a == H) { continue; } for(auto [b, w] : adj[a]) { if(arr[b] == 0) { dist[b][st] = 0; pq.push({-dist[b][st], {-st, b}}); continue; } if(dist[b][st] == -1 || d + w < dist[b][st]) { dist[b][st] = d + w; pq.push({-dist[b][st], {-st, b}}); } if(arr[b] == 2 && st < K) { ++st; if(dist[b][st] == -1 || (d + w) / 2 < dist[b][st]) { dist[b][st] = (d + w) / 2; pq.push({-dist[b][st], {-st, b}}); } --st; } } } double ans = -1; for(int i = 0; i <= K; ++i) { if(ans == -1 || (dist[H][i] != -1 && ans > dist[H][i])) 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...