Submission #42124

#TimeUsernameProblemLanguageResultExecution timeMemory
42124XmtosXJakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
8 ms1316 KiB
#include <bits/stdc++.h> using namespace std; int n,p[30004],b[30004],m; priority_queue <pair<int,int> ,vector <pair<int,int> >,greater <pair<int,int> > > pq; bool vis[30004]; vector <int> v[30004]; int cur[30004]; void dij() { for (int i=1;i<n;i++) cur[i]=INT_MAX; for (int i=0;i<v[b[0]].size();i++) cur[v[b[0]][i]]=0,pq.push({0,v[b[0]][i]}); while (!pq.empty()) { int x= (pq.top()).second; int y= (pq.top()).first; pq.pop(); if (vis[x]) continue; vis[x]=true; for (int i=0;i*p[x]+b[x]<n;i++) { int a= (i*p[x]+b[x]); for (int j=0;j<v[a].size();j++) { if (cur[v[a][j]]>i+y) { pq.push({i+y,v[a][j]}); cur[v[a][j]]=i+y; } } } for (int i=1;b[x]-i*p[x]>=0;i++) { int a= (b[x]-i*p[x]); for (int j=0;j<v[a].size();j++) { if (cur[v[a][j]]>i+y) { pq.push({i+y,v[a][j]}); cur[v[a][j]]=i+y; } } } } } int main() { cin >>n>>m; for (int i=0;i<m;i++) { cin >>b[i]>>p[i]; v[b[i]].push_back(i); } dij(); if (cur[1]==INT_MAX) cout <<-1; else cout <<cur[1]; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void dij()':
skyscraper.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[b[0]].size();i++)
                   ^
skyscraper.cpp:25:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0;j<v[a].size();j++)
                           ^
skyscraper.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0;j<v[a].size();j++)
                           ^
#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...