Submission #1275936

#TimeUsernameProblemLanguageResultExecution timeMemory
1275936mhn_neekJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
1095 ms3412 KiB
// IN THE NAME OF GOD #include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops,fast-math,omit-frame-pointer,no-stack-protector") #pragma GCC target("avx,avx2,fma,sse4.2,popcnt") typedef int lli; typedef pair<lli,lli> pii; typedef vector<lli> ve; typedef vector<pii> vp; const lli N = 8e4 + 100; const lli INF = 1e9; #define PB push_back #define MP make_pair #define fi first #define se second #define FOR(x,y) for(lli x = 0; x < y; x ++) #define FORS(x,y) for(lli x = 1; x <= y; x ++) lli n,m; lli B[N],P[N]; lli dis[N]; bool mark[N]; ve hehe[N]; int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; FOR(i,m){ cin>>B[i]>>P[i]; hehe[B[i]].PB(i); } FOR(i,m+n) dis[i] = INF; priority_queue<pii,vp,greater<pii>> pq; pq.push(MP(0,0)); dis[0] = 0; while(pq.size()){ lli v = pq.top().se; lli D = pq.top().fi; pq.pop(); if(D != dis[v] || mark[v])continue; mark[v] = 1; if(v >= m){ for(auto u : hehe[v-m]){ if(dis[u] > dis[v]){ dis[u] = dis[v]; pq.push(MP(dis[u],u)); } } } else{ for(lli i = B[v]%P[v]; i < n;i += P[v]){ lli u = i + m; lli fa = abs(i-B[v]); if(v != u && fa%P[v] == 0){ lli w = fa/P[v]; if(dis[u] > dis[v] + w){ dis[u] = dis[v] + w; pq.push(MP(dis[u],u)); } } } } } if(dis[1] == INF)dis[1] = -1; cout<<dis[1]<<endl; }
#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...