Submission #537368

#TimeUsernameProblemLanguageResultExecution timeMemory
537368GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
396 ms262144 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int maxn=3e4+5; const int B = 180; int n,m,st,fn; int dis[maxn * B]; bool vis[maxn * B]; vector<pair<int,int>>E[maxn * B]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; int sq = sqrt(n)+1; for(int i = 0;i < n;i++){ for(int j = 1;j < sq;j++){ E[i * sq + j].push_back({i * sq,0}); if(i - j >= 0) E[i * sq + j].push_back({(i - j) * sq + j,1}); if(i + j < n) E[i * sq + j].push_back({(i + j) * sq + j,1}); } } for(int i = 0;i < m;i++){ int b,p; cin >> b >> p; if(i == 0) st = b; if(i == 1) fn = b; if(p < sq) E[b * sq].push_back({b * sq + p,0}); else { for(int j = 1;b - j * p >= 0;j++) E[b * sq].push_back({(b - j * p) * sq,j}); for(int j = 1;b + j * p < n;j++) E[b * sq].push_back({(b + j * p) * sq,j}); } } for(int i = 0;i < n * sq;i++) dis[i] = 1e9; // cout<<st<<' '<<fn<<'\n'; 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; // cout<<x<<'\n'; for(auto i : E[x]){ if(dis[i.first] > dis[x] + i.second){ dis[i.first] = dis[x] + i.second; q.push({-dis[i.first],i.first}); } } } 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...