Submission #1093176

#TimeUsernameProblemLanguageResultExecution timeMemory
1093176alexander707070Cyberland (APIO23_cyberland)C++17
97 / 100
3075 ms2097152 KiB
#include<bits/stdc++.h> #define MAXN 100007 using namespace std; const long double inf=1e15; struct edge{ int to,s; long double cost; inline friend bool operator < (edge fr,edge sc){ return fr.cost>sc.cost; } }; int n,m,k; vector<edge> v[MAXN][31]; long double dist[MAXN][31]; long double ans; bool vis[MAXN][31]; int ability[MAXN]; priority_queue<edge> q; bool li[MAXN]; bool dfs(int x,int y){ if(x==y)return true; li[x]=true; bool res=false; for(edge e:v[x][0]){ if(li[e.to])continue; if(dfs(e.to,y))res=true; } return res; } long double gg(long double d,int a,int b){ if(a>b)return d/2; return d; } void dijkstra(){ while(!q.empty()){ edge curr=q.top(); q.pop(); if(vis[curr.to][curr.s])continue; //vis[curr.to][curr.s]=true; for(edge e:v[curr.to][curr.s]){ if(vis[e.to][e.s] or dist[e.to][e.s]<=gg(dist[curr.to][curr.s],curr.s,e.s)+e.cost)continue; dist[e.to][e.s]=gg(dist[curr.to][curr.s],curr.s,e.s)+e.cost; q.push({e.to,e.s,dist[e.to][e.s]}); } } } void reset(){ for(int i=1;i<=n;i++)li[i]=false; for(int i=1;i<=n;i++){ for(int f=0;f<=k;f++){ v[i][f].clear(); vis[i][f]=false; } } } double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr){ n=N; m=M; k=K; H++; reset(); for(int i=1;i<=m;i++){ X[i-1]++; Y[i-1]++; for(int f=0;f<=k;f++){ if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]}); if(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]}); if(f>0 and arr[X[i-1]-1]==2 and X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f-1,C[i-1]}); if(f>0 and arr[Y[i-1]-1]==2 and Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f-1,C[i-1]}); } } if(!dfs(1,H))return -1; for(int i=1;i<=n;i++){ for(int f=0;f<=k;f++){ dist[i][f]=inf; } } for(int i=1;i<=n;i++){ ability[i]=arr[i-1]; if((li[i] and ability[i]==0) or i==1){ dist[i][k]=0; q.push({i,k,0}); } } dijkstra(); ans=dist[H][k]; for(int i=0;i<=k;i++){ ans=min(ans,dist[H][i]); } return ans; } /*int main(){ cout<<solve(3,2,0,2,{0,1},{1,0},{5,4},{1,2,1})<<"\n"; cout<<solve(3,2,0,2,{0,1},{1,2},{5,4},{1,2,1})<<"\n"; cout<<solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1})<<"\n"; cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1})<<"\n"; return 0; }*/

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:85:66: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   85 |             if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]});
      |                                                                  ^
cyberland.cpp:86:66: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   86 |             if(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]});
      |                                                                  ^
cyberland.cpp:88:97: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   88 |             if(f>0 and arr[X[i-1]-1]==2 and X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f-1,C[i-1]});
      |                                                                                                 ^
cyberland.cpp:89:97: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   89 |             if(f>0 and arr[Y[i-1]-1]==2 and Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f-1,C[i-1]});
      |                                                                                                 ^
#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...