Submission #1186340

#TimeUsernameProblemLanguageResultExecution timeMemory
1186340MalixJakarta Skyscrapers (APIO15_skyscraper)C++20
100 / 100
482 ms7352 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; int main() { // ios::sync_with_stdio(0); // cin.tie(0); int n,m;cin>>n>>m; vector<set<int>> b(n); int s,e; REP(i,0,m){ int x,y;cin>>x>>y; if(i==0)s=x; else if(i==1)e=x; b[x].insert(y); } vi dist(n,inf); dist[s]=0; priority_queue<pi,vector<pi>,greater<pi>> pq; pq.push({dist[s],s}); while(!pq.empty()){ int x=pq.top().F; int y=pq.top().S; pq.pop(); if(dist[y]<x)continue; for(auto z:b[y]){ int tmp=z; int c=1; while(y+z<n){ if(dist[y+z]>x+c){ dist[y+z]=x+c; pq.push({dist[y+z],y+z}); } z+=tmp; c++; } z=tmp;c=1; while(y-z>=0){ if(dist[y-z]>x+c){ dist[y-z]=x+c; pq.push({dist[y-z],y-z}); } z+=tmp; c++; } } } int ans=dist[e]; if(ans==inf)cout<<-1; else cout<<ans; }
#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...