Submission #955011

#TimeUsernameProblemLanguageResultExecution timeMemory
955011BbtTJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms604 KiB
#include<bits/stdc++.h> using namespace std; struct ed{ int n,w; }; bool operator<(ed a,ed b){ return a.w<b.w; } int N,M,d[30005]; bitset<30005> vis; vector<vector<ed>> edge; int main(){ cin>>N>>M; edge.resize(N); for(int i=0;i<M;i++){ int b,p; scanf("%d%d",&b,&p); edge.push_back({}); edge[b].push_back((ed){edge.size()-1,0}); for(int j=b+p;j<N;j+=p){ edge.back().push_back((ed){j,(j-b)/p}); } for(int j=b-p;j>=0;j-=p){ edge.back().push_back((ed){j,(b-j)/p}); } } priority_queue<ed> Q; Q.push((ed){0,0}); while(!Q.empty()){ int cur=Q.top().n,wn=Q.top().w; Q.pop(); vis[cur]=1; for(auto togo:edge[cur]){ if(vis[togo.n])continue; if(d[togo.n]>wn+togo.w||d[togo.n]==0){ d[togo.n]=wn+togo.w; Q.push((ed){togo.n,d[togo.n]}); } } }cout<<d[1]<<endl; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:43: warning: narrowing conversion of '(edge.std::vector<std::vector<ed> >::size() - 1)' from 'std::vector<std::vector<ed> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   25 |         edge[b].push_back((ed){edge.size()-1,0});
      |                                ~~~~~~~~~~~^~
skyscraper.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d",&b,&p);
      |         ~~~~~^~~~~~~~~~~~~~
#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...