제출 #1125445

#제출 시각아이디문제언어결과실행 시간메모리
1125445ASN49KJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
1100 ms97220 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() #define pb push_back #define bug(a) std::cerr << "(" << #a << ": " << a << ")\n"; using i64 = long long; const int N=100'000; struct cord { int pos,step; bool operator <(const cord &b)const { if(pos==b.pos) { return step<b.step; } return pos<b.pos; } bool operator ==(const cord &b)const { return pos==b.pos && step==b.step; } }; map<cord , int>dist[N]; vector<int>adj[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; vector<cord>cords(m); for(auto &c:cords) { cin>>c.pos>>c.step; adj[c.pos].push_back(c.step); } deque<cord>q; q.push_front(cords[0]); vector<bool>viz(n,0); auto insert=[&](cord nextt,int cost,bool fronted) { if(!dist[nextt.pos].count(nextt) || dist[nextt.pos][nextt]>cost) { dist[nextt.pos][nextt]=cost; if(fronted) { q.push_front(nextt); } else { q.push_back(nextt); } } }; while(q.size()) { //assert(dist[nextt.pos].size()<=6'000'000); cord then=q.front(); int then_cost=dist[then.pos][then]; q.pop_front(); if(then.pos==cords[1].pos) { cout<<then_cost<<'\n'; return 0; } if(!viz[then.pos]) { viz[then.pos]=true; for(auto &c:adj[then.pos]) { insert((cord){then.pos , c} , then_cost , true); } adj[then.pos].clear(); } if(then.pos>=then.step) { insert({then.pos-then.step , then.step} , then_cost+1 , false); } if(then.pos+then.step<n) { insert({then.pos+then.step , then.step} , then_cost+1 , false); } } 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...