Submission #545746

#TimeUsernameProblemLanguageResultExecution timeMemory
545746AJ00Jakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
216 ms130616 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; vector<vector<pair<int,int>>> adj(30000); signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int t=1,n,k,st,fin,B,P; cin >> n >> k; // pair<int,int> doge[k]; vector<set<int>> doges(n); vector<int> dist(n); // memset(dist, 0x3f, sizeof dist); for (int i = 0; i < k; i++){ cin >> B >> P; doges[B].insert(P); if (i == 0){ st = B; } if (i == 1){ fin = B; } } //sort(doge,doge+k); for (int i = 0; i < n; i++){ for (int jump: doges[i]){ for (int j = i+jump; j < n; j += jump){ adj[i].push_back({j,((j-i)/jump)}); if (doges[j].find(jump) != doges[j].end()){ break; } } for (int j = i-jump; j >= 0; j -= jump){ adj[i].push_back({j,((i-j)/jump)}); if (doges[j].find(jump) != doges[j].end()){ break; } } } } for (int i = 0; i < n; i++){ dist[i] = INF; } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0,st}); dist[st] = 0; while(!pq.empty()){ int distp = pq.top().first; int p = pq.top().second; pq.pop(); if (distp != dist[p]){ continue; } for (auto ch: adj[p]){ if (dist[p] + ch.second < dist[ch.first]){ dist[ch.first] = dist[p] + ch.second; pq.push({dist[ch.first],ch.first}); } } } dist[fin] >= INF ? cout << "-1\n" : cout << dist[fin] << "\n"; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:10:9: warning: unused variable 't' [-Wunused-variable]
   10 |     int t=1,n,k,st,fin,B,P;
      |         ^
skyscraper.cpp:48:12: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     dist[st] = 0;
      |            ^
skyscraper.cpp:63:13: warning: 'fin' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     dist[fin] >= INF ? cout << "-1\n" : cout << dist[fin] << "\n";
      |             ^
#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...