제출 #163016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163016		giorgikob	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	3 ms	1784 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){
			cout<<dist<<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});
				}
			}
		}
	}
	
	cout<<-1<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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