Submission #806717

#TimeUsernameProblemLanguageResultExecution timeMemory
806717TheSahibCyberland (APIO23_cyberland)C++17
68 / 100
3067 ms91624 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define ll long long #define pii pair<int, char> using namespace std; const ll oo = 1e18; const int MAX = 1e5 + 5; struct edge{ int u, c; }; int n, k, f; int A[MAX]; vector<edge> g[MAX]; bool visited[MAX]; vector<int> starts; void dfs(int node){ visited[node] = 1; for(auto& e:g[node]){ if(visited[e.u]) continue; dfs(e.u); } } double dist[MAX][32]; bool comp(pii a, pii b){ return dist[a.first][a.second] <= dist[b.first][b.second]; } void dijkstra(){ set<pii, decltype(&comp)> st(&comp); for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { dist[i][j] = oo; } } for(int a:starts){ dist[a][k] = 0; st.insert({a, k}); } while(!st.empty()){ int node = st.begin()->first; int l = st.begin()->second; double d = dist[node][l]; st.erase(st.begin()); for(auto& e:g[node]){ double b = d + e.c; if(b < dist[e.u][l]){ st.erase({e.u, l}); dist[e.u][l] = b; st.insert({e.u, l}); } if(l == 0 || A[e.u] != 2) continue; if(b / 2 < dist[e.u][l - 1]){ st.erase({e.u, l - 1}); dist[e.u][l - 1] = b / 2; st.insert({e.u, l - 1}); } } } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { n = N; k = K; f = H; starts.clear(); for (int i = 0; i < n; i++) { A[i] = arr[i]; g[i].clear(); visited[i] = 0; } 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]}); } g[f].clear(); dfs(0); starts.push_back(0); for (int i = 0; i < n; i++) { if(visited[i] && A[i] == 0){ starts.push_back(i); } } dijkstra(); double ans = oo; for(int i = 0; i <= k; ++i){ ans = min(ans, dist[f][i]); } if(ans == oo){ return -1; } else{ return ans; } }

Compilation message (stderr)

cyberland.cpp: In function 'bool comp(std::pair<int, char>, std::pair<int, char>)':
cyberland.cpp:31:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |     return dist[a.first][a.second] <= dist[b.first][b.second];
      |                          ~~^~~~~~
cyberland.cpp:31:55: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |     return dist[a.first][a.second] <= dist[b.first][b.second];
      |                                                     ~~^~~~~~
#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...