Submission #739463

#TimeUsernameProblemLanguageResultExecution timeMemory
739463MauveJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
75 ms141688 KiB
#include<bits/stdc++.h> using namespace std; #define ll int #define ss second #define ff first #define INF 2000000000000000 #define pb push_back #define edge pair<ll, pair<ll,ll> > // une, number ,power #define cost first #define num second.first #define pwr second.second ll n,m,l,r,i,j,ii,jj,k,x,y,D[30005][172],s,e; vector< edge > v[30005][172]; // number , power (powergu oroi bol power = 179) int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n>>m; for(i=1;i<=m;i++){ cin>>l>>r; if(i==1) s=l; if(i==2) e=l; if(r>170) for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){ edge a; a.num=l+r*j; a.pwr=171; a.cost=j; if(a.num<n) v[l][171].pb(a); a.num=l-r*j; if(a.num>=0) v[l][171].pb(a); } else{ v[l][171].pb({0,{l,r}}); } } priority_queue<edge , vector< edge >, greater< edge > > q; memset(D,-1,sizeof(D)); q.push({0,{s,171}}); while(!q.empty()){ ll une, nmbr, power; une=q.top().cost; nmbr=q.top().num; power=q.top().pwr; q.pop(); if(D[nmbr][power]==-1){ D[nmbr][power]=une; for(edge no : v[nmbr][power]) if(D[no.num][no.pwr]==-1) q.push({une+no.cost,{no.num,no.pwr}}); if(power!=171){ ll poo=nmbr+power,pp=nmbr-power; if(D[nmbr][171]==-1) q.push({une,{nmbr,171}}); if(poo<n && D[poo][power]==-1) q.push({++une,{poo,power}}); if(pp>=0 && D[pp][power]==-1) q.push({une,{pp,power}}); } } } cout<<D[e][171]; }
#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...