Submission #251704

#	Time	Username	Problem	Language	Result	Execution time	Memory
251704		define	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	159 ms	10220 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 998244353;
constexpr int inf = 3e18;

int N,M;
vector<int>v[30005];
int dist[30005];
signed main(){
	cin>>N>>M;
	int start,goal;
	rep(i,M){
		int a,b;cin>>a>>b;
		v[a].push_back(b);
		if(!i)start=a;
		if(i==1)goal=a;
	}
	rep(i,N){
		sort(all(v[i]));v[i].erase(unique(all(v[i])),v[i].end());
	}
	priority_queue<P,vector<P>,greater<P>>que;
	fill(dist,dist+N,inf);
	dist[start]=0;
	que.push({0,start});
	while(!que.empty()){
		P p=que.top();que.pop();
		if(dist[p.second]<p.first)continue;
		for(int i:v[p.second]){
			for(int j=p.second+i;j<N;j+=i){
				if(dist[j]>p.first+(j-p.second)/i){
					dist[j]=p.first+(j-p.second)/i;
					que.push({dist[j],j});
				}
				if(lower_bound(all(v[j]),i)!=v[j].end()&&*lower_bound(all(v[j]),i)==i)break;
			}
			for(int j=p.second-i;j>=0;j-=i){
				if(dist[j]>p.first+(p.second-j)/i){
					dist[j]=p.first+(p.second-j)/i;
					que.push({dist[j],j});
				}
				if(lower_bound(all(v[j]),i)!=v[j].end()&&*lower_bound(all(v[j]),i)==i)break;
			}
		}
	}
	cout<<(dist[goal]!=inf?dist[goal]:-1)<<endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:61:18: warning: 'goal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<(dist[goal]!=inf?dist[goal]:-1)<<endl;
         ~~~~~~~~~^

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