Submission #1187194

#TimeUsernameProblemLanguageResultExecution timeMemory
1187194WarinchaiJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
220 ms222736 KiB
#include<bits/stdc++.h> using namespace std; map<pair<int,int>,vector<int>>mp; vector<pair<int,int>>adj[4000005]; int dis[4000005]; int inf=1e15; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,m;cin>>n>>m; int st=0,en=0; for(int i=0;i<m;i++){ int b,p;cin>>b>>p; if(i==0)st=b; if(i==1)en=b; mp[{b%p,p}].push_back(b); } int id=n-1; for(auto x:mp){ int cur=x.first.first; int p=x.first.second; for(auto b:x.second)adj[b].push_back({id+(b-cur)/p+1,0}); for(cur;cur<n;cur+=p){ id++; adj[id].push_back({cur,0}); if(cur!=x.first.first)adj[id-1].push_back({id,1}); } cur=x.first.first; for(auto b:x.second)adj[b].push_back({id+(b-cur)/p+1,0}); for(cur;cur<n;cur+=p){ id++; adj[id].push_back({cur,0}); if(cur!=x.first.first)adj[id].push_back({id-1,1}); } } mp.clear(); for(int i=0;i<=id;i++)dis[i]=inf; deque<pair<int,int>>dq; dq.push_back({0,st}); while(!dq.empty()){ auto [d,u]=dq.front(); dq.pop_front(); if(d>=dis[u])continue; dis[u]=d; for(auto v:adj[u]){ if(v.second)dq.push_back({d+1,v.first}); else dq.push_front({d,v.first}); } } if(dis[en]==inf)cout<<-1; else cout<<dis[en]; }

Compilation message (stderr)

skyscraper.cpp:6:9: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
    6 | int inf=1e15;
      |         ^~~~
#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...