oj.uz

Submission #975486

# Submission time Handle Problem Language Result Execution time Memory
975486 2024-05-05T10:05:02 Z batsukh2006 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 352 KB 
#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+1,1e9);
	q.push({0,st});
	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[1];
	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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -