Submission #898024

#TimeUsernameProblemLanguageResultExecution timeMemory
898024votranngocvyJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
223 ms113764 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define piii pair<pii,int> #define fi first #define se second const int N = 3e4 + 5; bitset<N>vis[N]; int n,m,s,t,a[N],b[N]; vector<int>vec[N]; int bfs() { queue<piii>q; q.push({{a[1],b[1]},0}); vis[a[1]][b[1]] = true; while (!q.empty()) { int u = q.front().fi.fi,steps = q.front().fi.se,d = q.front().se; q.pop(); if (u == a[2]) return d; if (u - steps >= 0 && !vis[u - steps][steps]) { vis[u - steps][steps] = true; q.push({{u - steps,steps},d + 1}); } if (u + steps < n && !vis[u + steps][steps]) { vis[u + steps][steps] = true; q.push({{u + steps,steps},d + 1}); } for (auto x: vec[u]) { if (u - x >= 0 && !vis[u - x][x]) { vis[u - x][x] = true; q.push({{u - x,x},d + 1}); } if (u + x < n && !vis[u + x][x]) { vis[u + x][x] = true; q.push({{u + x,x},d + 1}); } } } return -1; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> a[i] >> b[i]; vec[a[i]].push_back(b[i]); } cout << bfs() << "\n"; }
#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...