Submission #968320

#TimeUsernameProblemLanguageResultExecution timeMemory
968320SyriusCyberland (APIO23_cyberland)C++17
68 / 100
1163 ms154424 KiB
#include <bits/stdc++.h> #include "cyberland.h" using namespace std; // #define int long long #define ll long long #define ff first #define ss second #define pint pair < double , int > #define vint vector < int > #define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL) const ll inf = 1e18 + 9; const int mxn = 2e5 + 2; const int mod = 1e9 + 7; vector < vector < pint > > adj(mxn); vint arr_; double dis[32][mxn]; bool vis[mxn]; priority_queue < pint > q[32]; void dfs(int x , int par , int H) { if (vis[x]) return; vis[x] = 1; if (x == H) return; if (arr_[x] == 0) q[0].push({0 , x}); for (pint i : adj[x]) { if (i.ss == par) continue; dfs(i.ss , x , H); } } double solve(int n , int m , int k , int H , vint x , vint y , vint c , vint arr) { for (int i = 0; i < n; i++) { adj[i].clear(); vis[i] = 0; } for (int i = 0; i <= k; i++) { for (int j = 0; j < n; j++) { dis[i][j] = -1; } } arr_ = arr; for (int i = 0; i < m; i++) { adj[x[i]].push_back({c[i] , y[i]}); adj[y[i]].push_back({c[i] , x[i]}); } dfs(0 , 0 , H); q[0].push({0 , 0}); for (int i = 0; i <= k; i++) { while (!q[i].empty()) { pint p = q[i].top(); q[i].pop(); if (dis[i][p.ss] != -1) continue; dis[i][p.ss] = -p.ff; if (p.ss == H) continue; for (pint j : adj[p.ss]) { q[i].push({p.ff - j.ff , j.ss}); if (arr[j.ss] == 2) q[i+1].push({(p.ff - j.ff) / 2 , j.ss}); } } } double ans = inf; for (int i = 0; i <= k; i++) { if (dis[i][H] != -1) ans = min(ans , dis[i][H]); } return (ans == inf) ? -1 : 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...