제출 #1191404

#제출 시각아이디문제언어결과실행 시간메모리
1191404ArdelionJakarta Skyscrapers (APIO15_skyscraper)C++20
36 / 100
74 ms24136 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("O3") //#pragma GCC target("avx2") using namespace std; //#define int long long #define ll long long #define X first #define Y second #define lc (id<<1) #define rc (lc|1) #define mid ((l+r+1)>>1) #define pb push_back #define lb lower_bound #define ub upper_bound #define mp make_pair #define sep ' ' #define endl "\n" #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define FileIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(x) x.begin(), x.end() #define ret(x) {cout << x << endl; return;} typedef pair<int, int> pii; typedef pair<ll , ll > pll; const int N = 3e3+13; const int LOG = 23; const int MOD = 1e9 + 7; //998244353; //1e9+9; const int INF = 1e9; //1e18; const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; ll md(ll x) {x%=MOD; return (x < 0 ? x+MOD : x);} ll GCD(ll _a, ll _b) { return (!_b ? _a : GCD(_b, _a % _b)); } ll POW(ll _a, ll _b) { return !_b ? 1 : ((_b & 1 ? _a : 1) * POW(_a * _a % MOD, _b / 2)) % MOD;} int n, m, s, f; int dist[N][N], P[N]; vector<int> b[N]; void BFS() { deque<pii> q; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { dist[i][j] = INF; } } dist[s][0] = 0; q.push_back(mp(s, 0)); pii p; while(!q.empty()) { p = q.front(); q.pop_front(); for(int d : b[p.X]) { if(dist[p.X][d] > dist[p.X][p.Y]) { dist[p.X][d] = dist[p.X][p.Y]; q.push_front(mp(p.X, d)); } } if(p.X - P[p.Y] >= 0 && dist[p.X-P[p.Y]][p.Y] > dist[p.X][p.Y] + 1) { dist[p.X-P[p.Y]][p.Y] = dist[p.X][p.Y] + 1; q.push_back(mp(p.X-P[p.Y], p.Y)); } if(p.X + P[p.Y] < n && dist[p.X+P[p.Y]][p.Y] > dist[p.X][p.Y] + 1) { dist[p.X+P[p.Y]][p.Y] = dist[p.X][p.Y] + 1; q.push_back(mp(p.X+P[p.Y], p.Y)); } } } void F() { cin >> n >> m; int x; for(int i = 0; i < m; i++) { cin >> x >> P[i]; if(i == 0) s = x; else if(i == 1) f = x; b[x].pb(i); } BFS(); cout << (dist[f][1] == INF ? -1 : dist[f][1]); } int32_t main() { migmig; //PREP(); int t=1; //cin >> t; while(t--) F(); 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...