Submission #153065

#	Time	Username	Problem	Language	Result	Execution time	Memory
153065		songc	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	5 ms	2680 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(S, 0));
	while (!PQ.empty()){
		int x, d;
		tie(x,d) = 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(x-v*i, d+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(x+v*i, d+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: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43