Submission #163012

#	Time	Username	Problem	Language	Result	Execution time	Memory
163012		giorgikob	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	21 ms	1792 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(){
	
	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++){
		
		for(int j=X[i];j<=n;j+=P[i]){
			for(int k=0;k<V[j].size();k++){
				gr[i].push_back( { V[j][k], (j-X[i])/P[i] });
			}
		}
		
		for(int j=X[i]-P[i];j>=1;j-=P[i]){
			for(int k=0;k<V[j].size();k++){
				gr[i].push_back( { V[j][k], (X[i]-j)/P[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 x = p.second;
		int dist = p.first;
		
		for(int i=0;i<gr[x].size();i++){
			int to = gr[x][i].first;
			if(D[to] > dist + gr[x][i].second){
				
				s.erase({D[to],to});
				D[to] = dist + gr[x][i].second;
				s.insert({D[to],to});
			}
		}
		
	}
	
	cout<<D[2]<<endl;
}

Compilation message (stderr)

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

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