제출 #703986

#제출 시각아이디문제언어결과실행 시간메모리
703986ToroTNJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1099 ms83752 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define X first #define Y second int n,m,b[30005],p[30005],d[30005],u,cnt,num,cost,block=173; vector<int> v[30005]; priority_queue<pair<int,int> > pq; set<int> go[175][175]; int main() { ios_base::sync_with_stdio(0),cin.tie(0); cin >> n >> m; for(int i=0;i<n;i++) { for(int j=1;j<=block;j++) { go[j][i%j].insert(i); } d[i]=1e9; } for(int i=1;i<=m;i++) { cin >> b[i] >> p[i]; v[b[i]].pb(p[i]); } d[b[1]]=0; pq.push({0,b[1]}); while(!pq.empty()) { u=pq.top().Y; pq.pop(); for(int i=1;i<=block;i++) { if(go[i][u%i].find(u)!=go[i][u%i].end()) { go[i][u%i].erase(u); } } for(auto dis:v[u]) { if(dis>block) { cnt=0; for(int i=u;i>0;i-=dis) { if(d[u]+cnt<d[i]) { d[i]=d[u]+cnt; pq.push({-d[i],i}); } ++cnt; } cnt=0; for(int i=u;i<n;i+=dis) { if(d[u]+cnt<d[i]) { d[i]=d[u]+cnt; pq.push({-d[i],i}); } ++cnt; } }else { for(auto it=go[dis][u%dis].begin();it!=go[dis][u%dis].end();it++) { num=(*it); cost=abs(u-num)/dis; if(d[u]+cost<d[num]) { d[num]=d[u]+cost; pq.push({-d[num],num}); } } } } } if(d[b[2]]==1e9) { printf("-1\n"); }else { printf("%d\n",d[b[2]]); } }
#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...