Submission #163020

#	Time	Username	Problem	Language	Result	Execution time	Memory
163020		giorgikob	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1078 ms	3960 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = 3e4 + 69;
 
int n,m;
 
vector<int>V[N];
 
vector< pair<int,int> >gr[N];
 
int X[N],P[N],D[N];
 
set< pair<int,int> > s;
 
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>X[i]>>P[i];
		X[i]++;
		V[X[i]].push_back(i);
	}
	
	for(int i=1;i<=m;i++){
		
		
		if(i>1){
			D[i] = 1e9;
			s.insert({1e9,i});
		}
	}
	
	D[1] = 0;
	s.insert({0,1});
	
	while(s.size()){
		
		pair<int,int> p = *(s.begin());
		
		s.erase(s.begin());
		
		int i = p.second;
		int dist = p.first;
		
		if(i==2){
			if(D[2]==1e9)D[2]=-1;
			cout<<D[2]<<endl;
			return 0;
		}
		
		for(int j=X[i];j<=n;j+=P[i]){
			for(int k=0;k<V[j].size();k++){
				
				int to = V[j][k];
				if(D[to] > dist + (j-X[i])/P[i]){
					
					s.erase({D[to],to});
					D[to] = dist + (j-X[i])/P[i];
					s.insert({D[to],to});
				}
			}
		}
		
		for(int j=X[i]-P[i];j>=1;j-=P[i]){
			for(int k=0;k<V[j].size();k++){
				
				int to = V[j][k];
				if(D[to] > dist + (X[i]-j)/P[i]){
					
					s.erase({D[to],to});
					D[to] = dist + (X[i]-j)/P[i];
					s.insert({D[to],to});
				}
			}
		}
	}
	if(D[2]==1e9)
	D[2] = -1;
	cout<<D[2]<<endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<V[j].size();k++){
                ~^~~~~~~~~~~~
skyscraper.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<V[j].size();k++){
                ~^~~~~~~~~~~~

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