제출 #536792

#제출 시각아이디문제언어결과실행 시간메모리
536792GurbanJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1100 ms90040 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]; unordered_map<int,int>dis; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; int mx = max(n,m) + 1; 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] * mx + p[0]] = 0; while(!q.empty()){ int idx = q.front().first; int pi = q.front().second; q.pop(); int now = dis[idx * mx + pi]; if(idx == b[1]) return cout<<now,0; if(idx - pi >= 0){ auto t = dis.find((idx - pi) * mx + pi); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[(idx - pi) * mx + pi] = now + 1; q.push({idx - pi,pi}); } } if(idx + pi < n){ auto t = dis.find((idx + pi) * mx + pi); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[(idx + pi) * mx + pi] = now + 1; q.push({idx + pi,pi}); } } for(auto i : v[idx]){ if(idx - i >= 0){ auto t = dis.find((idx - i) * mx + i); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[(idx - i) * mx + i] = now + 1; q.push({idx - i,i}); } } if(idx + i < n){ auto t = dis.find((idx + i) * mx + i); if(t == dis.end() or (t != dis.end() and (*t).second > now + 1)){ dis[(idx + i) * mx + 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...