Submission #1167984

#TimeUsernameProblemLanguageResultExecution timeMemory
1167984ZeroCoolJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
152 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ld long double #define all(v) v.begin(),v.end() #define ar array const int M = 1e6; const int N = 4e5 + 20; const int LOG = 61; const int INF = 1e18; const int MOD = 1e9 + 7; const ld EPS = 1e-9; inline void mm(int &x){x = (x % MOD + MOD) % MOD;} inline void chmin(int &x, int y){x = min(x, y);} inline void chmax(int &x, int y){x = max(x, y);} #pragma GCC optimize("unroll-loops,O3") void orz(){ int n, m; cin>>n>>m; vector<int> g[n]; int s = -1, e = -1; while(m--){ int a, b; cin>>a>>b; if(s == -1)s = a; else if(e == -1)e = a; if(b < n)g[a].push_back(b); } deque<ar<int, 2> > q; int dst[n][n]; memset(dst, -1, sizeof dst); dst[s][0] = 0; q.push_back({s, 0}); while(q.size()){ auto [x, j] = q.front(); q.pop_front(); //cout<<x<<" "<<j<<'\n'; for(auto u: g[x]){ if(dst[x][u] == -1){ dst[x][u] = dst[x][j]; q.push_front({x, u}); } } if(!j)continue; for(auto y: {x - j, x + j}){ if(y < 0 || y >= n)continue; if(dst[y][j] == -1){ dst[y][j] = dst[x][j] + 1; q.push_back({y, j}); } } } int ans = INF; for(int i = 0;i < n;i++){ if(dst[e][i] != -1)ans = min(ans, dst[e][i]); } if(ans >= INF)ans = -1; cout<<ans; } signed main(){ios_base::sync_with_stdio(false);cin.tie(0); int t = 1; //cin>>t; while(t--)orz(); }
#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...