Submission #975488

#	Time	Username	Problem	Language	Result	Execution time	Memory
975488		batsukh2006	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	561 ms	4044 KiB

skyscraper

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
using namespace std;
 
#define MOD 1000000009
//#define int long long
#define ff first
#define ss second
#define endl '\n'
typedef pair<int,int> pp;
void solve(){
	int n,m; cin>>n>>m;
	int st,ed;
	vector<int> v[n];
	for(int i=0; i<m; i++){
		int b,p; cin>>b>>p;
		if(i==0) st=b;
		if(i==1) ed=b;
		v[b].push_back(p);
	}
	priority_queue<pp,vector<pp>,greater<pp> > q;
	vector<int> dis(n,1e9);
	q.push({0,st});
	dis[st]=0;
	while(!q.empty()){
		int d=q.top().ff;
		int c=q.top().ss;
		q.pop();
		if(d<=dis[c]){
			for(auto p: v[c]){
				for(int i=c,k=0; i<n; i+=p,k++){
					if(d+k<dis[i]){
						dis[i]=d+k;
						q.push({d+k,i});
					}
				}
				for(int i=c,k=0; i>=0; i-=p,k++){
					if(d+k<dis[i]){
						dis[i]=d+k;
						q.push({d+k,i});
					}
				}
			}
		}
	}
	if(dis[ed]!=1e9) cout<<dis[ed];
	else cout<<-1;
}
signed main(){
    // freopen("248.in", "r", stdin);
    // freopen("248.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;	
    while(t--){
        solve();
        cout<<endl;
    }
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:64:11: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |  if(dis[ed]!=1e9) cout<<dis[ed];
      |           ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43