Submission #1195279

#TimeUsernameProblemLanguageResultExecution timeMemory
1195279SarvarJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; int32_t 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]; } vector<vector<int>> doges_at(N); // binodagi dogelar for (int i = 0; i < M; i++) { doges_at[B[i]].push_back(i); } int tot = N + M; vector<int> dist(tot, INF); deque<int> dq; dist[N + 0] = 0; // doge 0 dan boshlaymiz dq.push_back(N + 0); vector<bool> used(N, false); // binoda faqat bir marta uzatamiz while (!dq.empty()) { int u = dq.front(); dq.pop_front(); if (u >= N) { // bu doge int j = u - N; int b = B[j], p = P[j]; for (int d = -1; d <= 1; d += 2) { int nb = b + d * p; if (nb >= 0 && nb < N && dist[nb] > dist[u] + 1) { dist[nb] = dist[u] + 1; dq.push_back(nb); } } } else { // bu bino if (used[u]) continue; used[u] = true; for (int j : doges_at[u]) { int v = N + j; if (dist[v] > dist[u]) { dist[v] = dist[u]; dq.push_front(v); } } } } int res = dist[N + 1]; cout << (res == INF ? -1 : res) << "\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...