Submission #536663

#TimeUsernameProblemLanguageResultExecution timeMemory
536663GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1094 ms41500 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #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; if(idx == b[1]) return cout<<dis[{idx,pi}],0; 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}); } } } } cout<<-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...