Submission #536661

#TimeUsernameProblemLanguageResultExecution timeMemory
536661GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1092 ms45140 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int maxn=3e4+5; int n,m; int b[maxn],p[maxn]; vector<int>v[maxn]; set<pair<int,int>>vis; map<pair<int,int>,int>dis; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0;i < m;i++){ cin >> b[i] >> p[i]; v[b[i]].push_back(p[i]); } priority_queue<tuple<int,int,int>>q; q.push({0,b[0],p[0]}); dis[{b[0],p[0]}] = 0; while(!q.empty()){ int idx = get<1>(q.top()); int pi = get<2>(q.top()); q.pop(); if(vis.find({idx,pi}) != vis.end()) continue; vis.insert({idx,pi}); int now = dis[{idx,pi}]; if(idx - pi >= 0){ auto t = dis.find({idx - pi,pi}); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[{idx - pi,pi}] = now + 1; q.push({-now - 1,idx - pi,pi}); } } if(idx + pi < n){ auto t = dis.find({idx + pi,pi}); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[{idx + pi,pi}] = now + 1; q.push({-now - 1,idx + pi,pi}); } } for(auto i : v[idx]){ if(idx - i >= 0){ auto t = dis.find({idx - i,i}); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[{idx - i,i}] = now + 1; q.push({-now - 1,idx - i,i}); } } if(idx + i < n){ auto t = dis.find({idx + i,i}); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[{idx + i,i}] = now + 1; q.push({-now - 1,idx + i,i}); } } } } int ans = 1e9; for(auto i : dis){ if(i.first.first == b[1]){ ans = min(ans,i.second); } } if(ans == 1e9) cout<<-1; else cout<<ans; }
#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...