Submission #1275827

#TimeUsernameProblemLanguageResultExecution timeMemory
1275827namiousJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
1096 ms3224 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> B(m), P(m); for (int i = 0; i < m; i++) { cin >> B[i] >> P[i]; // اگر ورودی 1-based باشه: // B[i]--; } // برای هر موقعیت، سگ‌هایی که اونجا هستن vector<vector<int>> dogs_at_pos(n); for (int i = 0; i < m; i++) { dogs_at_pos[B[i]].push_back(i); } vector<int> dist(m, INF); using pii = pair<int,int>; priority_queue<pii, vector<pii>, greater<pii>> pq; dist[0] = 0; pq.push({0, 0}); while (!pq.empty()) { auto [d,u] = pq.top(); pq.pop(); if (d != dist[u]) continue; if (u == 1) break; // جواب پیدا شد int bu = B[u], pu = P[u]; int rem = bu % pu; // همه‌ی موقعیت‌هایی که دوج u می‌تونه برسه for (int x = rem; x < n; x += pu) { int cost = abs(x - bu) / pu; // همه‌ی دوج‌هایی که سر این موقعیت هستن for (int v : dogs_at_pos[x]) { int nd = d + cost; if (nd < dist[v]) { dist[v] = nd; pq.push({nd, v}); } } } } if (dist[1] == INF) cout << -1 << "\n"; else cout << dist[1] << "\n"; return 0; }
#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...