Submission #537218

#TimeUsernameProblemLanguageResultExecution timeMemory
537218GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1050 ms247548 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int maxn=3e4+5; const int B = 87; int n,m; int b[maxn],p[maxn]; int ver[maxn][B]; 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 = 85; int sz = n - 1; for(int i = 0;i < n;i++) for(int j = 1;j <= sq;j++) ver[i][j] = ++sz; for(int i = 0;i < n;i++){ for(int j = 1;j <= sq;j++){ E[ver[i][j]].push_back({i,0}); // E[i].push_back({ver[i][j],0}); if(i - j >= 0) E[ver[i][j]].push_back({ver[i-j][j],1}); if(i + j < n) E[ver[i][j]].push_back({ver[i+j][j],1}); } } for(int i = 0;i < m;i++){ cin >> b[i] >> p[i]; if(p[i] <= sq) E[b[i]].push_back({ver[b[i]][p[i]],0}); else { for(int j = 1;b[i] - j * p[i] >= 0;j++) E[b[i]].push_back({b[i] - j * p[i],j}); for(int j = 1;b[i] + j * p[i] < n;j++) E[b[i]].push_back({b[i] + j * p[i],j}); } } // cout<<E[22][0].first<<' '<<E[22][0].second<<'\n'; // assert(sz) for(int i = 0;i <= sz;i++) dis[i] = 1e9; dis[b[0]] = 0; priority_queue<pair<int,int>>q; q.push({0,b[0]}); 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[b[1]] == 1e9) cout<<-1; else cout<<dis[b[1]]; }
#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...