Submission #450419

#TimeUsernameProblemLanguageResultExecution timeMemory
450419sobaJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1087 ms86340 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 30001; int dist[N]; vector<pair<int,int> >v[N]; int b[N] , p[N] ; vector<pair<int,int> >vp; int n , m ; map<pair<int,int> , int>mp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int x , y; cin>> n>> m ; for(int i = 0 ; i < m ; i++) { cin >> b[i] >> p[i]; if(i==0)x=b[i]; if(i==1)y=b[i]; mp[{b[i],p[i]}]++; if(mp[{b[i],p[i]}]>1)continue; vp.push_back({b[i], p[i]}); } if(x==y) { cout << 0 ; return 0; } sort(vp.begin(),vp.end()); m=vp.size(); for(int i = 0 ; i < m ; i++) { int c=1; for(int j = vp[i].first+vp[i].second ; j< n ; j+= vp[i].second) { v[vp[i].first].push_back({j , c}); c++; if(mp[{j,vp[i].second}]) break; } } for(int i = m-1 ; i >=0 ; i--) { int c=1; for(int j = vp[i].first-vp[i].second ; j>=0 ; j-= vp[i].second) { v[vp[i].first].push_back({j , c}); c++; if(mp[{j,vp[i].second}]) break; } } priority_queue<pair<int,int> >q; for (int i = 0; i <= n; i++) dist[i] = 1e9; dist[x] = 0; q.push({0,x}); while (!q.empty()) { int a = q.top().second; int ot= q.top().first; q.pop(); if(a==y) { cout << 0-ot; return 0; } //cout << a << " : " ; for (auto u : v[a]) { int b = u.first, w = u.second; // cout << b << " "; if (dist[a]+w < dist[b]) { dist[b] = dist[a]+w; q.push({-dist[b],b}); } } //cout << "\n"; } cout << -1; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:58:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     dist[x] = 0;
      |     ~~~~~~~~^~~
skyscraper.cpp:65:9: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         if(a==y)
      |         ^~
#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...