Submission #153066

#	Time	Username	Problem	Language	Result	Execution time	Memory
153066		songc	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1082 ms	70828 KiB

skyscraper

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

int N, M, S, E;
set<int> chk[30303];
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);
	}
	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++){
				if (chk[x-v*i].find(v) != chk[x-v*i].end()) break;
				chk[x-v*i].insert(v);
				PQ.push(pii(d+i, x-v*i));
			}
			for (int i=1; x+v*i<N; i++){
				if (chk[x+v*i].find(v) != chk[x+v*i].end()) break;
				chk[x+v*i].insert(v);
				PQ.push(pii(d+i, x+v*i));
			}
		}
	}
	printf("%d\n", D[E]);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:13: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:16: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: 21 / 21
• Subtask 5: 0 / 43