Submission #1026293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026293		xnqs	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	159 ms	87548 KiB

skyscraper

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int64_t x, d;
int64_t src, dest;
int64_t dist[30005][175];
std::vector<int64_t> dogs_less_than_sqrt[30005];
std::vector<int64_t> dogs_greater_than_sqrt[30005];

int64_t bfs(int64_t src, int64_t dest) {
	memset(dist,0x3f,sizeof(dist));
	std::priority_queue<std::tuple<int64_t,int64_t,int64_t>, std::vector<std::tuple<int64_t,int64_t,int64_t>>, std::greater<std::tuple<int64_t,int64_t,int64_t>>> q;
	q.emplace(0,src,0);
	dist[src][0] = 0;

	while (!q.empty()) {
		auto [c, k, cap] = q.top();
		q.pop();

		// switch dog (<= sqrt)
		for (const auto& i : dogs_less_than_sqrt[k]) {
			if (dist[k][i]>dist[k][cap]) {
				dist[k][i] = dist[k][cap];
				q.emplace(dist[k][i], k, i);
			}
		}

		// try to go as far as possible (> sqrt)
		for (const auto& i : dogs_greater_than_sqrt[k]) {
			for (int64_t j = 1; k+j*i < x; j++) {
				if (dist[k+j*i][0]>dist[k][cap]+j) {
					dist[k+j*i][0] = dist[k][cap]+j;
					q.emplace(dist[k+j*i][0], k+j*i, 0);
				}
			}
			for (int64_t j = 1; k-j*i >= 0; j++) {
				if (dist[k-j*i][0]>dist[k][cap]+j) {
					dist[k-j*i][0] = dist[k][cap]+j;
					q.emplace(dist[k+j*i][0], k-j*i, 0);
				}
			}
		}

		// use the current dog (<= sqrt)
		if (k-cap>=0&&dist[k-cap][cap]>dist[k][cap]+1) {
			dist[k-cap][cap] = dist[k][cap]+1;
			q.emplace(dist[k-cap][cap], k-cap, cap);
		}
		if (k+cap<x&&dist[k+cap][cap]>dist[k][cap]+1) {
			dist[k+cap][cap] = dist[k][cap]+1;
			q.emplace(dist[k+cap][cap], k+cap, cap);
		}
	}

	int64_t ret = 0x3f3f3f3f3f3f3f3f;
	for (int64_t i = 0; i < 175; i++) {
		ret = std::min(ret, dist[dest][i]);
	}

	return ((ret==0x3f3f3f3f3f3f3f3f) ? -1 : ret);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> d;

	for (int64_t i = 0, a, b; i < d; i++) {
		std::cin >> a >> b;
		if (i==0) {
			src = a;
		}
		else if (i==1) {
			dest = a;
		}

		if (b<=173) {
			dogs_less_than_sqrt[a].emplace_back(b);
		}
		else {
			dogs_greater_than_sqrt[a].emplace_back(b);
		}
	}

	for (int64_t i = 1; i <= x; i++) {
		std::sort(dogs_less_than_sqrt[i].begin(), dogs_less_than_sqrt[i].end());
		std::sort(dogs_greater_than_sqrt[i].begin(), dogs_greater_than_sqrt[i].end());
		dogs_less_than_sqrt[i].erase(std::unique(dogs_less_than_sqrt[i].begin(), dogs_less_than_sqrt[i].end()),
		                             dogs_less_than_sqrt[i].end());
		dogs_greater_than_sqrt[i].erase(std::unique(dogs_greater_than_sqrt[i].begin(), dogs_greater_than_sqrt[i].end()),
		                             dogs_greater_than_sqrt[i].end());
	}

	std::cout << bfs(src,dest) << "\n";
}

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