Submission #115654

#	Time	Username	Problem	Language	Result	Execution time	Memory
115654		imyujin	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	696 ms	6120 KiB

skyscraper

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

#define MAXN 30005
#define MAXM 30005
#define LINF 8100000000ll
#define fi first
#define se second

typedef pair<int, int> pi;

long long dp[MAXN];
int B[MAXM], P[MAXM];
vector<int> d[MAXN];
priority_queue<pi, vector<pi>, greater<pi> > pq;

int main(){
	int N, M;

	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++) scanf("%d%d", B+i, P+i);

	for(int i=0; i<M; i++) d[B[i]].push_back(P[i]);
	for(int i=0; i<N; i++){
		sort(d[i].begin(), d[i].end());
		unique(d[i].begin(), d[i].end());
	}

	pq.push(make_pair(0, B[0]));
	for(int i=0; i<N; i++) dp[i]=LINF;
	dp[B[0]]=0;
	while(!pq.empty()){
		pi t=pq.top();
		pq.pop();
		if(t.se==B[1]){
			printf("%lld", dp[B[1]]);
			return 0;
		}
		for(int j=0; j<d[t.se].size(); j++){
			int l=t.se+d[t.se][j];
			for(int k=1; l<N; k++, l+=d[t.se][j]){
				if(t.fi+k<dp[l]){
					dp[l]=t.fi+k;
					pq.push(make_pair(t.fi+k, l));
				}
				//if(lower_bound(d[l].begin(), d[l].end(), d[t.se][j])!=d[l].end()) break;
			}
			l=t.se-d[t.se][j];
			for(int k=1; l>=0; k++, l-=d[t.se][j]){
				if(t.fi+k<dp[l]){
					dp[l]=t.fi+k;
					pq.push(make_pair(t.fi+k, l));
				}
				//if(lower_bound(d[l].begin(), d[l].end(), d[t.se][j])!=d[l].end()) break;
			}
		}
	}

	printf("-1");
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<d[t.se].size(); j++){
                ~^~~~~~~~~~~~~~~
skyscraper.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:25:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<M; i++) scanf("%d%d", B+i, P+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~

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