Submission #153067

#	Time	Username	Problem	Language	Result	Execution time	Memory
153067		songc	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	906 ms	262148 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, S, E;
vector<int> V[30303];
int D[30303];
priority_queue<pii, vector<pii>, greater<pii>> PQ;

int main(){
	scanf("%d %d", &N, &M);
	for (int i=1; i<=M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		if (i == 1) S = x;
		if (i == 2) E = x;
		V[x].push_back(y);
	}
	for (int i=0; i<N; i++) sort(V[i].begin(), V[i].end());
	memset(D, -1, sizeof D);
	PQ.push(pii(0, S));
	while (!PQ.empty()){
		int x, d;
		tie(d,x) = PQ.top();
		PQ.pop();
		if (D[x] != -1) continue;
		D[x] = d;
		for (int v : V[x]){
			for (int i=1; x-v*i>=0; i++){
				PQ.push(pii(d+i, x-v*i));
				auto it = lower_bound(V[x-v*i].begin(), V[x-v*i].end(), v);
				if (it != V[x-v*i].end() && *it == v) break;
			}
			for (int i=1; x+v*i<N; i++){
				PQ.push(pii(d+i, x+v*i));
				auto it = lower_bound(V[x+v*i].begin(), V[x+v*i].end(), v);
				if (it != V[x+v*i].end() && *it == v) break;
			}
		}
	}
	printf("%d\n", D[E]);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:12: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:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

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