Submission #1202977

#TimeUsernameProblemLanguageResultExecution timeMemory
1202977rshohruhJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
1096 ms6076 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 1e18 const int MXN = 3e4 + 5; int b[MXN], p[MXN], dist[MXN]; vector<int> adj[MXN]; map<int, int> mp[MXN]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) dist[i] = inf; for (int i = 0; i < m; i++) { cin >> b[i] >> p[i]; adj[b[i]].push_back(p[i]); } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[b[0]] = 0; pq.push({0, b[0]}); while (!pq.empty()) { auto [k, u] = pq.top(); pq.pop(); if (k > dist[u]) continue; for (int v : adj[u]) { // if (mp[v].find(u % v) != mp[v].end()) continue; // mp[v][u % v]; for (int i = u - v; i >= 0; i -= v) { if (dist[i] > dist[u] + ((u - i) / v)) { dist[i] = dist[u] + ((u - i) / v); pq.push({dist[i], i}); } } for (int i = u + v; i < n; i += v) { if (dist[i] > dist[u] + ((i - u) / v)) { dist[i] = dist[u] + ((i - u) / v); pq.push({dist[i], i}); } } } } cout << (dist[b[1]] >= inf ? -1 : dist[b[1]]) << '\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...