Submission #536665

#TimeUsernameProblemLanguageResultExecution timeMemory
536665GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1099 ms24748 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]; 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]); } queue<pair<int,int>>q; q.push({b[0],p[0]}); dis[{b[0],p[0]}] = 0; while(!q.empty()){ int idx = q.front().first; int pi = q.front().second; q.pop(); if(idx == b[1]) return cout<<dis[{idx,pi}],0; 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({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({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({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({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...