Submission #18401

#TimeUsernameProblemLanguageResultExecution timeMemory
18401choyi0521Jakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
143 ms9212 KiB
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int MAX_N = 30000, RTN = 200; int n, m, dist[MAX_N], s, e; bool ck[MAX_N][RTN], fvis[MAX_N]; struct st{ int b, p, w; st(int _b, int _p, int _w) :b(_b), p(_p), w(_w){} }; vector<int> adj[MAX_N]; queue<st> q; int main(){ scanf("%d %d", &n, &m); for (int i = 0; i < m; i++){ int a, b; scanf("%d %d", &a, &b); adj[a].push_back(b); if (i == 0) s = a; if (i == 1) e = a; } dist[e] = -1; q.push(st(s, 0, 0)); while (!q.empty()){ st h = q.front(); q.pop(); if (h.b < 0 || h.b >= n) continue; if (abs(h.p) < RTN){ if (ck[h.b][abs(h.p)]) continue; ck[h.b][abs(h.p)] = true; } if (!fvis[h.b]){ fvis[h.b] = true; dist[h.b] = h.w; for (auto t : adj[h.b]){ q.push(st(h.b + t, t, h.w + 1)); q.push(st(h.b - t, -t, h.w + 1)); } } q.push(st(h.b + h.p, h.p, h.w + 1)); } printf("%d", dist[e]); 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...