Submission #879138

#TimeUsernameProblemLanguageResultExecution timeMemory
879138leanchecCyberland (APIO23_cyberland)C++17
97 / 100
2016 ms79884 KiB
#include "cyberland.h" #include<bits/stdc++.h> using namespace std; vector<pair<int,int>> adj[100100]; bool visited[100100]={}; void dfs(int cur, int H){ visited[cur]=true; for(int i=0; i<(int)adj[cur].size(); i++){ int viz=adj[cur][i].first; if(visited[viz] || viz==H)continue; dfs(viz, H); } } 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, 50); for(int i=0; i<N; i++){ adj[i].clear(); visited[i]=0; } for(int i=0; i<M; i++){ adj[x[i]].push_back({y[i], c[i]}); adj[y[i]].push_back({x[i], c[i]}); } double dist[100100][75], po[74]; bool achou[100100][75]; po[0]=1; for(int i=1; i<=69; i++)po[i]=po[i-1]*2; for(int i=0; i<N; i++){ for(int j=0; j<=K; j++){ dist[i][j]=1e15; achou[i][j]=0; } } set<array<double, 3>> ss; ss.insert({0, H, 0}); dist[H][0]=0; while(!ss.empty()){ array<double, 3> curtop=*ss.begin(); ss.erase(ss.begin()); int cur=curtop[1]; int curk=curtop[2]; if(achou[cur][curk])continue; achou[cur][curk]=true; for(int i=0; i<(int)adj[cur].size(); i++){ int viz=adj[cur][i].first; if(viz==H)continue; double w=adj[cur][i].second; if(arr[cur]==2 && curk+1<=K){ if(dist[viz][curk+1]>dist[cur][curk]+w/po[curk+1]){ ss.erase({dist[viz][curk+1], viz, curk+1}); dist[viz][curk+1]=dist[cur][curk]+w/po[curk+1]; ss.insert({dist[viz][curk+1], viz, curk+1}); } } if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){ ss.erase({dist[viz][curk], viz, curk}); dist[viz][curk]=dist[cur][curk]+w/po[curk]; ss.insert({dist[viz][curk], viz, curk}); } } } if(!achou[0][0])return -1; dfs(0, H); double ans=1e15; for(int i=0; i<N; i++){ if(!visited[i] || (i!=0 && arr[i]!=0))continue; for(int j=0; j<=K; j++){ ans=min(ans, dist[i][j]); } } if(ans<5e14)return ans; return -1; }

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:44:19: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   44 |     ss.insert({0, H, 0});
      |                   ^
cyberland.cpp:64:50: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   64 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                  ^~~
cyberland.cpp:64:59: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   64 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                       ~~~~^~
cyberland.cpp:66:51: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   66 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                   ^~~
cyberland.cpp:66:60: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   66 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                        ~~~~^~
cyberland.cpp:70:44: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   70 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                            ^~~
cyberland.cpp:70:49: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   70 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                                 ^~~~
cyberland.cpp:72:45: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   72 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                             ^~~
cyberland.cpp:72:50: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   72 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                                  ^~~~
#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...