Submission #212737

#	Time	Username	Problem	Language	Result	Execution time	Memory
212737		spdskatr	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	121 ms	7924 KiB

skyscraper

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <functional>
#include <utility>
#include <cstring>
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

int N, M, b[30005], po[30005], seen[30005], dists[30005];
set<int> doges[30005];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", b+i, po+i);
		doges[b[i]].insert(po[i]);
	}
	memset(dists, 0x3f, sizeof(dists));
	dists[b[0]] = 0;
	pq.push({ 0, b[0] });
	while (!pq.empty()) {
		pii p = pq.top(); pq.pop();
		int u = p.se;
		if (u == b[1]) {
			printf("%d\n", dists[u]);
			return 0;
		}
		if (dists[u] < p.fi) continue;
		for (int doge : doges[u]) {
			for (int i = 1; u - i * doge >= 0; i++) {
				int k = u - i * doge;
				if (dists[k] > dists[u] + i) {
					dists[k] = dists[u] + i;
					pq.push({ dists[k], k });
				}
				if (doges[k].find(doge) != doges[k].end()) break;
			}
			for (int i = 1; u + i * doge < N; i++) {
				int k = u + i * doge;
				if (dists[k] > dists[u] + i) {
					dists[k] = dists[u] + i;
					pq.push({ dists[k], k });
				}
				if (doges[k].find(doge) != doges[k].end()) break;
			}
		}
	}
	printf("-1\n");
}

Compilation message (stderr)

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

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