제출 #199218

#제출 시각아이디문제언어결과실행 시간메모리
199218Alexa2001Jakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1098 ms39672 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; map< pair<int,int>, int> dist; queue< pair<int,int> > q; void baga(int x, int curr) { reached[x] = 1; for(auto it : v[x]) if(!dist[{x, it}]) { dist[{x, it}] = curr + 1; q.push({x, it}); } } int solve() { if(pos[0] == pos[1]) return 0; baga(pos[0], 0); 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 == pos[1]) return curr; if(!reached[x+s]) baga(x+s, curr); } if(x - s >= 0 && !dist[{ x - s, s }]) { dist[{ x - s, s }] = curr + 1; q.push({x-s, s}); if(x - s == pos[1]) return curr; if(!reached[x-s]) baga(x-s, curr); } } 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...