제출 #537826

#제출 시각아이디문제언어결과실행 시간메모리
537826GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
10 / 100
2 ms1040 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int maxn=3e4+5; const int B = 190; int n,m,st,fn; int dis[maxn * B]; bool vis[maxn * B]; vector<int>doge[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; int sq = sqrt(n)+1; for(int i = 0;i < m;i++){ int b,p; cin >> b >> p; if(i == 0) st = b; if(i == 1) fn = b; doge[b].push_back(p); } for(int i = 0;i < n * sq;i++) dis[i] = 1e9; dis[st * sq] = 0; priority_queue<pair<int,int>>q; q.push({0,st * sq}); while(!q.empty()){ int x = q.top().second; q.pop(); if(vis[x]) continue; vis[x] = 1; int bb = x / sq; int pw = x % sq; if(!pw){ for(auto i : doge[bb]){ int to = bb * sq + i; if(dis[to] > dis[x]){ dis[to] = dis[x]; q.push({-dis[to],to}); } } } else { if(dis[bb * sq] > dis[x]){ dis[bb * sq] = dis[x]; q.push({-dis[bb*sq],bb*sq}); } if(pw < sq){ if(bb - pw >= 0 and dis[(bb - pw) * sq + pw] > dis[x] + 1){ dis[(bb - pw) * sq + pw] = dis[x] + 1; q.push({-dis[(bb - pw) * sq + pw],(bb - pw) * sq + pw}); } if(bb + pw < n and dis[(bb + pw) * sq + pw] > dis[x] + 1){ dis[(bb + pw) * sq + pw] = dis[x] + 1; q.push({-dis[(bb + pw) * sq + pw],(bb + pw) * sq + pw}); } } else { for(int i = 1;;i++){ int to = bb - pw * i; if(to < 0) break; if(dis[to * sq] > dis[x] + i){ dis[to * sq] = dis[x] + i; q.push({-dis[to * sq],to * sq}); } } for(int i = 1;;i++){ int to = bb + pw * i; if(to >= n) break; if(dis[to * sq] > dis[x] + i){ dis[to * sq] = dis[x] + i; q.push({-dis[to * sq],to * sq}); } } } } } if(dis[fn * sq] == 1e9) cout<<-1; else cout<<dis[fn * sq]; }
#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...