Submission #851386

#TimeUsernameProblemLanguageResultExecution timeMemory
851386mychecksedadCyberland (APIO23_cyberland)C++17
26 / 100
1659 ms2097156 KiB
// #include "cyberland.h" #include<bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define all(x) x.begin(), x.end() const int SZ = 1e6; int _H; double po[35]; vector<pair<int, double>> g[SZ]; vector<bool> VIS; void dfs(int v, int p){ VIS[v] = 1; for(auto U: g[v]){ int u = U.first; if(u != p && u != _H) dfs(u, v); } } 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) { for(int i = 0; i < N; ++i) g[i].clear(); _H = H; VIS.clear(); VIS.resize(N); po[0] = 1; for(int i = 1; i < 35; ++i) po[i] = po[i - 1] * 2; vector<vector<double>> dist(N); vector<vector<bool>> vis(N); for(int i = 0; i < M; ++i) g[x[i]].pb({y[i], c[i]}), g[y[i]].pb({x[i], c[i]}); for(int i = 0; i < N; ++i) dist[i].resize(K + 1, -1), vis[i].resize(K + 1); dist[H][0] = 0; priority_queue<array<double, 3>> Q; Q.push({0, H, 0}); while(!Q.empty()){ int v = Q.top()[1], k = Q.top()[2]; Q.pop(); if(vis[v][k]) continue; vis[v][k] = 1; for(auto U: g[v]){ int u = U.first; if(u == H) continue; double w = U.second; if(arr[v] == 2 && (dist[u][k + 1] == -1 || dist[u][k + 1] > dist[v][k] + w / po[k + 1])){ dist[u][k + 1] = dist[v][k] + w / po[k + 1]; Q.push({-dist[u][k + 1], u, k + 1}); } if(dist[u][k] == -1 || dist[u][k] > dist[v][k] + w / po[k]){ dist[u][k] = dist[v][k] + w / po[k]; Q.push({-dist[u][k], u, k}); } } } if(!vis[0][0]) return -1; double ans = -1; dfs(0, 0); for(int i = 0; i < N; ++i){ if(VIS[i] && (arr[i] == 0 || i == 0)){ for(int j = 0; j <= K; ++j){ if(dist[i][j] == -1) continue; ans = ans == -1 || ans > dist[i][j] ? dist[i][j] : ans; } } } return ans; }

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:14: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   43 |   Q.push({0, H, 0});
      |              ^
cyberland.cpp:56:33: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   56 |        Q.push({-dist[u][k + 1], u, k + 1});
      |                                 ^
cyberland.cpp:56:38: warning: narrowing conversion of '(k + 1)' from 'int' to 'double' [-Wnarrowing]
   56 |        Q.push({-dist[u][k + 1], u, k + 1});
      |                                    ~~^~~
cyberland.cpp:60:29: warning: narrowing conversion of 'u' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.push({-dist[u][k], u, k});
      |                             ^
cyberland.cpp:60:32: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   60 |        Q.push({-dist[u][k], u, k});
      |                                ^
#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...