제출 #452093

#제출 시각아이디문제언어결과실행 시간메모리
452093Sarah_MokhtarJakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
1092 ms189632 KiB
//Sorry but iam targeting IOI :)) //NEVER LOSE HOPE #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> #define endl "\n" #define ceil(a,b) (a+(b-1))/b #define all(v) v.begin(),v.end() #define Hidden ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); using namespace std; const int N=3e4+10,mod = 1e9+7; int n,m,f[N],dis[N]; pair<int,int>a[N]; set<pair<int,int>>adj[N]; int main(){ cin>>n>>m; for(int i=0;i<m;++i){ cin>>a[i].first>>a[i].second; f[a[i].first]++; } for(int i=0;i<m;++i){ for(int j=a[i].first+a[i].second;j<=n;j+=a[i].second){ if(!f[j]) continue; adj[a[i].first].insert({j,((j-a[i].first)/a[i].second)}); } for(int j=a[i].first-a[i].second;j>=0;j-=a[i].second){ if(!f[j]) continue; adj[a[i].first].insert({j,((a[i].first-j)/a[i].second)}); } } priority_queue<pair<int,int>>pq; pq.push({0,a[0].first}); for(int i=0;i<N;++i) dis[i]=INT_MAX; dis[a[0].first]=0; while(!pq.empty()){ pair<int,int>p=pq.top(); pq.pop(); int u=p.second; for(auto i:adj[u]){ int cost=dis[u]+i.second; if(cost<dis[i.first]){ dis[i.first]=cost; pq.push({-cost,i.first}); } } } if(dis[a[1].first]==INT_MAX) cout<<"-1\n"; else cout<<dis[a[1].first]<<'\n'; }
#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...