Submission #777493

#TimeUsernameProblemLanguageResultExecution timeMemory
777493groshiCyberland (APIO23_cyberland)C++17
97 / 100
3079 ms94156 KiB
#include<bits/stdc++.h> #pragma GCC optimize "unroll-loops" #pragma GCC optimize "O3" #include "cyberland.h" using namespace std; struct wi{ vector<int> Q; double dp[71]; int co; int odw=0; }*w; vector<int> moge; void dfs(int x,int nie) { w[x].odw=1; if(x==nie) return; if(w[x].co==0) moge.push_back(x); for(int i=0;i<w[x].Q.size();i+=2) if(w[w[x].Q[i]].odw==0) dfs(w[x].Q[i],nie); } 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++) { if(x[i]!=h) w[x[i]].Q.push_back(y[i]),w[x[i]].Q.push_back(c[i]); if(y[i]!=h) w[y[i]].Q.push_back(x[i]),w[y[i]].Q.push_back(c[i]); } for(int i=0;i<n;i++) w[i].co=arr[i]; moge.clear(); dfs(0,h); moge.push_back(0); 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]=1e14; for(int i=0;i<moge.size();i++) { kolejka.push({0.0,{moge[i],0}}); for(int j=0;j<=k;j++) w[moge[i]].dp[j]=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; 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].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=1e14; for(int i=0;i<=k;i++) minn=min(minn,w[h].dp[i]); if(minn==1e14) return -1; else return minn; }

Compilation message (stderr)

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