제출 #199214

#제출 시각아이디문제언어결과실행 시간메모리
199214Alexa2001Jakarta Skyscrapers (APIO15_skyscraper)C++17
10 / 100
6 ms1144 KiB
#include <bits/stdc++.h> using namespace std; /// 12:08 const int Nmax = 30005; vector<int> v[Nmax]; int salt[Nmax], pos[Nmax]; bool reached[Nmax]; int n, m; int solve() { map< pair<int,int>, int> dist; queue< pair<int,int> > q; q.push({pos[0], salt[0]}); dist[ {pos[0], salt[0]} ] = 1; while(q.size()) { int x, s; tie(x, s) = q.front(); q.pop(); int curr = dist[{ x, s }]; if(x + s < n && !dist[{ x + s, s }]) { dist[{ x + s, s }] = curr + 1; q.push({x+s, s}); } if(x - s >= 0 && !dist[{ x - s, s }]) { dist[{ x - s, s }] = curr + 1; q.push({x-s, s}); } if(!reached[x]) { reached[x] = 1; if(x == pos[1]) return curr - 1; for(auto it : v[x]) if(!dist[{ x, it }]) { dist[{ x, it }] = curr; q.push({x, it}); } } } return -1; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); cin >> n >> m; int i; for(i=0; i<m; ++i) { cin >> pos[i] >> salt[i]; v[pos[i]].push_back(salt[i]); } cout << solve() << '\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...