제출 #163026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163026		giorgikob	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	18 ms	1916 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],fix[N];
 
priority_queue< 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.push({0,1});
	
	while(!s.empty()){
		
		pair<int,int> p = s.top();
		
		s.pop();
		
		
		
		int i = p.second;
		if(fix[i])continue;
		fix[i] = 1;
		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]){
					
					D[to] = dist + (j-X[i])/P[i];
					s.push({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] ){
					
					D[to] = dist + (X[i]-j)/P[i];
					s.push({D[to],to});
				}
			}
		}
	}
	if(D[2]==1e9)
	D[2] = -1;
	cout<<D[2]<<endl;
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<V[j].size();k++){
                ~^~~~~~~~~~~~
skyscraper.cpp:68: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: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43