Submission #1228122

#TimeUsernameProblemLanguageResultExecution timeMemory
1228122goduadzesabaCyberland (APIO23_cyberland)C++20
44 / 100
1223 ms2162688 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; const long long inf=1e18; bool u[100005]; vector <pair<int,long long> > v[100005]; vector <int> pt; int h; void dfs(int i){ u[i]=1; if (i==h) return; for (auto j:v[i]){ if (!u[j.first]) dfs(j.first); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { for (int i=0; i<N; i++) v[i].clear(); h=H; for (int i=0; i<M; i++){ v[x[i]].push_back({y[i],c[i]}); v[y[i]].push_back({x[i],c[i]}); } arr[0]=0; set <array<double,3> > s; double d[N][K+1]; for (int i=0; i<N; i++){ for (int j=0; j<=K; j++) d[i][j]=inf; } d[0][0]=0; for (int i=0; i<N; i++) u[i]=0; dfs(0); for (int i=0; i<N; i++){ if (arr[i]==0 && u[i]){ s.insert({0,(double)i,0}); d[i][0]=0; } } while (!s.empty()){ int X=(*s.begin())[1],Y=(*s.begin())[2]; s.erase(s.begin()); for (auto i:v[X]){ if (d[i.first][Y]>d[X][Y]+i.second){ s.erase({d[i.first][Y],(double)i.first,(double)Y}); d[i.first][Y]=d[X][Y]+i.second; s.insert({d[i.first][Y],(double)i.first,(double)Y}); } } for (auto i:v[X]){ if (arr[i.first]!=2) continue; if (d[i.first][Y+1]>(d[X][Y]+i.second)/2){ s.erase({d[i.first][Y+1],(double)i.first,(double)Y+1}); d[i.first][Y+1]=(d[X][Y]+i.second)/2; s.insert({d[i.first][Y+1],(double)i.first,(double)Y+1}); } } } //for (int i=0; i<N; i++) cout<<i<<" -> "<<d[i]<<"\n"; double mn=inf; for (int i=0; i<=K; i++) mn=min(mn,d[H][i]); if (mn==inf) return -1; return mn; }
#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...