Submission #1069503

#TimeUsernameProblemLanguageResultExecution timeMemory
1069503LuvidiJakarta Skyscrapers (APIO15_skyscraper)C++17
22 / 100
419 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll, ll> #define pii pair<int, int> #define fs first #define sc second #define pb push_back void solve() { int n,m; cin>>n>>m; pii a[m]; vector<pair<int,bool>> adj[n*m+n]; for(int i=0;i<m;i++){ int b,p; cin>>b>>p; a[i]={b,p}; for(int x=b%p;x<n;x++){ adj[n*i+x].pb({n*m+x,0}); } adj[n*m+b].pb({n*i+b,0}); for(int x=b%p;x+p<n;x++){ adj[n*i+x].pb({n*i+x+p,1}); adj[n*i+x+p].pb({n*i+x,1}); } } int dist[n*m+n]; for(int i=0;i<n*m+n;i++)dist[i]=1e9; dist[a[0].fs]=0; deque<int> dq; dq.push_back(a[0].fs); while(!dq.empty()){ int v=dq.front(); dq.pop_front(); for(auto[u,w]:adj[v]){ if(dist[v]+w<dist[u]){ dist[u]=dist[v]+w; if(w)dq.push_back(u); else dq.push_front(u); } } } int ans=dist[n+a[1].fs]; if(ans==1e9)ans=-1; cout<<ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }
#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...