Submission #450421

#TimeUsernameProblemLanguageResultExecution timeMemory
450421sobaJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1086 ms81732 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 ; set<pair<int,int> >s; for(int i = 0 ; i < m ; i++) { cin >> b[i] >> p[i]; if(i==0)x=b[i]; if(i==1)y=b[i]; s.insert({b[i], p[i]}); } if(x==y) { cout << 0 ; return 0; } for(auto u : s) { int c=1; for(int j = u.first+u.second ; j< n ; j+= u.second) { v[u.first].push_back({j , c}); c++; if(mp[{j,u.second}]) break; } } for(auto u : s) { int c=1; for(int j = u.first-u.second ; j>=0 ; j-= u.second) { v[u.first].push_back({j , c}); c++; if(mp[{j,u.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:26:5: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |     if(x==y)
      |     ^~
skyscraper.cpp:26:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...