Submission #108296

#	Time	Username	Problem	Language	Result	Execution time	Memory
108296		maruii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	686 ms	3620 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

priority_queue<pii, vector<pii>, greater<pii> > pq;
int dst[30000];
vector<int> edge[30000];
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M, st, ed; cin>>N>>M;
	for(int i=0; i<M; ++i){
		int b,p; cin>>b>>p;
		edge[b].push_back(p);
		if(!i) st = b;
		else if(i==1) ed = b;
	}

	fill(dst, dst+N, 1e9);
	pq.emplace(0, st); dst[st] = 0;
	while(pq.size()){
		auto x = pq.top(); pq.pop();
		if(x.ff != dst[x.ss]) continue;
		for(auto p: edge[x.ss]){
			for(int j=0; x.ss+p*j<N; ++j){
				if(dst[x.ss+p*j] > x.ff + j){
					dst[x.ss+p*j] = x.ff + j;
					pq.emplace(x.ff + j, x.ss+p*j);
				}
			}
			for(int j=1; x.ss-p*j>=0; ++j){
				if(dst[x.ss-p*j] > x.ff + j){
					dst[x.ss-p*j] = x.ff + j;
					pq.emplace(x.ff + j, x.ss-p*j);
				}
			}
		}
	}

	cout<<(dst[ed]==1e9?-1:dst[ed]);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:21:29: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pq.emplace(0, st); dst[st] = 0;
                     ~~~~~~~~^~~
skyscraper.cpp:41:15: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<(dst[ed]==1e9?-1:dst[ed]);
         ~~~~~~^

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