Submission #777182

#TimeUsernameProblemLanguageResultExecution timeMemory
777182groshiCyberland (APIO23_cyberland)C++17
97 / 100
3055 ms169080 KiB
#include<bits/stdc++.h> #include "cyberland.h" using namespace std; struct wi{ vector<int> Q; double dp[203]; int co; int odw=0; }*w; double solve(int32_t n,int32_t m,int32_t k,int32_t h,vector<int32_t> x,vector<int32_t> y,vector<int32_t> c, vector<int32_t> arr) { w=new wi[n+3]; for(int i=0;i<m;i++) { w[x[i]].Q.push_back(y[i]); w[y[i]].Q.push_back(x[i]); w[x[i]].Q.push_back(c[i]); w[y[i]].Q.push_back(c[i]); } for(int i=0;i<n;i++) w[i].co=arr[i]; priority_queue<pair<double,pair<int,int> > > kolejka; k=min(k,70); for(int i=0;i<n;i++) for(int j=0;j<=k;j++) w[i].dp[j]=1e18; kolejka.push({0.0,{0,0}}); while(!kolejka.empty()) { auto para=kolejka.top(); kolejka.pop(); int x=para.second.first; int typ=para.second.second; double ile=-para.first; if(ile>w[x].dp[typ]) continue; if(x==h) continue; for(int i=0;i<w[x].Q.size();i+=2) { int pom=w[x].Q[i]; double dodaj=w[x].Q[i+1]; if(w[pom].co==0) { if(w[pom].dp[typ]==0.0) continue; w[pom].dp[typ]=0.0; kolejka.push({0.0,{pom,typ}}); continue; } if(w[pom].dp[typ]>ile+dodaj) kolejka.push({-ile-dodaj,{pom,typ}}),w[pom].dp[typ]=ile+dodaj; if(w[pom].co!=2) continue; dodaj+=ile; dodaj/=2; if(w[pom].dp[typ+1]>dodaj && typ+1<=k) kolejka.push({-dodaj,{pom,typ+1}}),w[pom].dp[typ+1]=dodaj; } } double minn=1e18; for(int i=0;i<=k;i++) minn=min(minn,w[h].dp[i]); if(minn==1e18) return -1; else return minn; }

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int32_t, int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0;i<w[x].Q.size();i+=2)
      |                     ~^~~~~~~~~~~~~~
#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...