Submission #350631

#	Time	Username	Problem	Language	Result	Execution time	Memory
350631		Fischer	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	3 ms	2668 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e4 + 10;
set<int> pos[maxn];
vector<pair<int, int>> g[maxn];
using ll = long long;
ll d[maxn];

ll dijkstra(int src, int snk) {
	memset(d, 1, sizeof d);
	d[src] = 0;
	using pii = pair<ll, int>;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({0, src});
	while (!Q.empty()) {
		auto q = Q.top(); Q.pop();
		if (q.second == snk) return q.first;
		if (q.first != d[q.second]) continue;
		for (auto e : g[q.second]) {
			ll temp = q.first + e.second;
			if (temp < d[e.first]) {
				d[e.first] = temp;
				Q.push({temp, e.first});
			}
		}
	}
	return -1;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a;
	set<pair<int, int>> t;
	for (int i = 0; i < m; ++i) {
		int b, p;
		cin >> b >> p;
		t.insert({p, b});
		pos[b].insert(p);
	}
	auto same = [](int b, int p) {
		return !pos[b].empty() && pos[b].count(p);	
	};
	for (auto q : t) {
		for (int i = 1; ; ++i) {
			int temp = q.second + i * q.first;
			if (temp >= n) break;
			g[q.second].emplace_back(temp, i);
			if (same(temp, q.first)) break;
		}
		for (int i = 1; ; ++i) {
			int temp = q.second - i * q.first;
			if (temp < 0) break;
			g[q.second].emplace_back(temp, i);
			if (same(temp, q.first)) break;
		}
	}
	cout << dijkstra(0, 1) << endl;
	return 0;
}

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