Submission #969794

#TimeUsernameProblemLanguageResultExecution timeMemory
969794pccJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
205 ms183348 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 tlll tuple<ll,ll,ll> const int inf = 1e9; const int mxn = 3e4+10; const int mxe = mxn*sqrt(mxn)*2; const int mxv = mxe; map<pii,vector<int>> mp; int N,M; int ecnt,vcnt; int to[mxe],nid[mxe],wei[mxe]; int head[mxv]; int dist[mxv]; int S,T; void add_edge(int a,int b,int w){ ecnt++; nid[ecnt] = head[a]; to[ecnt] = b; wei[ecnt] = w; head[a] = ecnt; } deque<pii> dq; void BFS(){ fill(dist,dist+mxv,inf); dist[S] = 0; dq.push_back(pii(0,S)); while(!dq.empty()){ auto [d,now] = dq.front(); dq.pop_front(); if(d != dist[now])continue; for(int eid = head[now];eid;eid = nid[eid]){ int nxt = to[eid],w = wei[eid]; //cout<<now<<' '<<nxt<<":"<<dist[now]+w<<' '<<dist[nxt]<<endl; if(!w){ if(dist[nxt]>dist[now]){ dist[nxt] = dist[now]; dq.push_front(pii(dist[nxt],nxt)); } } else{ if(dist[nxt]>dist[now]+w){ dist[nxt] = dist[now]+w; dq.push_back(pii(dist[nxt],nxt)); } } } } return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>M; for(int i = 0;i<M;i++){ pii tmp; cin>>tmp.fs>>tmp.sc; mp[pii(tmp.sc,tmp.fs%tmp.sc)].push_back(tmp.fs); if(!i)S = tmp.fs; if(i == 1)T = tmp.fs; } vcnt = N-1; for(auto &i:mp){ sort(i.sc.rbegin(),i.sc.rend()); for(int j = i.fs.sc;j<N;j+=i.fs.fs){ vcnt++; add_edge(vcnt,j,0); while(!i.sc.empty()&&i.sc.back() == j){ add_edge(i.sc.back(),vcnt,0); i.sc.pop_back(); } if(j != i.fs.sc){ add_edge(vcnt-1,vcnt,1); add_edge(vcnt,vcnt-1,1); } } } BFS(); cout<<(dist[T]>=inf?-1:dist[T])<<'\n'; return 0; }
#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...