Submission #1026302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026302		xnqs	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	753 ms	35300 KiB

skyscraper

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

const int BLK_SIZE = 269;

int x, d;
int src, dest;
int dist[30005][BLK_SIZE+1];
std::vector<int> dogs_less_than_sqrt[30005];
std::vector<int> dogs_greater_than_sqrt[30005];
 
int bfs(int src, int dest) {
	memset(dist,0x3f,sizeof(dist));
	std::priority_queue<std::tuple<int,int,int>, std::vector<std::tuple<int,int,int>>, std::greater<std::tuple<int,int,int>>> q;
	q.emplace(0,src,0);
	dist[src][0] = 0;
 
	while (!q.empty()) {
		auto [c, k, cap] = q.top();
		q.pop();
 
		// switch dog (<= sqrt)
		if (dist[k][0]>dist[k][cap]) {
			dist[k][0] = dist[k][cap];
			q.emplace(dist[k][0], k, 0);
		}
		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 (int 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 (int 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 (cap!=0) {
			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);
			}
		}
	}
 
	int ret = 0x3f3f3f3f;
	for (int i = 0; i < BLK_SIZE; i++) {
		ret = std::min(ret, dist[dest][i]);
	}
 
	return ((ret==0x3f3f3f3f) ? -1 : ret);
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> x >> d;
 
	for (int i = 0, a, b; i < d; i++) {
		std::cin >> a >> b;
		if (i==0) {
			src = a;
		}
		else if (i==1) {
			dest = a;
		}
 
		if (b<=BLK_SIZE) {
			dogs_less_than_sqrt[a].emplace_back(b);
		}
		else {
			dogs_greater_than_sqrt[a].emplace_back(b);
		}
	}
 
	for (int i = 0; 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: 43 / 43