제출 #1195292

#제출 시각아이디문제언어결과실행 시간메모리
1195292SarvarJakarta 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); 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; dq.push_back(N + 0); vector<bool> used(N, false); while (!dq.empty()) { int u = dq.front(); dq.pop_front(); if (u >= N) { int j = u - N; int b = B[j], p = P[j]; int nb; nb = b + p; if (nb < N && dist[nb] > dist[u] + 1) { dist[nb] = dist[u] + 1; dq.push_back(nb); } nb = b - p; if (nb >= 0 && dist[nb] > dist[u] + 1) { dist[nb] = dist[u] + 1; dq.push_back(nb); } } else { 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 ans = dist[N + 1]; cout << (ans == INF ? -1 : ans) << "\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...