Submission #260914

#	Time	Username	Problem	Language	Result	Execution time	Memory
260914		atoiz	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	743 ms	116732 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cassert>
#include <tuple>

using namespace std;

const int MAXN = (1 << 15), QUEUE_SIZE = 40000000, CUTOFF = (1 << 8);
vector<int> powers[MAXN];
int dist[MAXN][CUTOFF];
int N, M, S, T;
tuple<int, int, int> qu[QUEUE_SIZE];
int top;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int b, p;
		cin >> b >> p;

		if (i == 0) S = b;
		else if (i == 1) T = b;

		powers[b].push_back(p);
		if (p >= CUTOFF) powers[b].push_back(-p);
	}

	for (int i = 0; i < N; ++i) for (int j = 0; j < CUTOFF; ++j) dist[i][j] = QUEUE_SIZE;

	qu[0] = make_tuple(S, 0, 0), top = 0;
	for (int qi = 0; qi <= top; ++qi) {
		int u, d, c;
		tie(u, d, c) = qu[qi];
		if (u == T) return cout << c << endl, 0;

		powers[u].push_back(d);

		for (int d0 : powers[u]) {
			if (abs(d0) < CUTOFF && dist[u][d0] == QUEUE_SIZE) dist[u][d0] = c;

			if (abs(d0) >= CUTOFF) {
				if (0 <= u + d0 && u + d0 < N) qu[++top] = make_tuple(u + d0, d0, c + 1);
			} else {
				if (u - d0 >= 0 && dist[u - d0][d0] == QUEUE_SIZE) {
					qu[++top] = make_tuple(u - d0, d0, dist[u - d0][d0] = c + 1);
				}

				if (u + d0 < N && dist[u + d0][d0] == QUEUE_SIZE) {
					qu[++top] = make_tuple(u + d0, d0, dist[u + d0][d0] = c + 1);
				}
			}
		}
		powers[u].clear();
	}
	cout << -1 << endl;
}

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