Submission #260897

#	Time	Username	Problem	Language	Result	Execution time	Memory
260897		atoiz	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1086 ms	73384 KiB

skyscraper

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

using namespace std;

const int MAXN = (1 << 15), QUEUE_SIZE = 40000000;
vector<int> powers[MAXN];
unordered_map<int, int> dist;
int N, M, S, T;
int qu[QUEUE_SIZE], 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);
	}

	qu[0] = S * MAXN, top = 0;
	for (int qi = 0; qi <= top; ++qi) {
		int u = qu[qi] / MAXN, d = qu[qi] & (MAXN - 1), c = dist[qu[qi]];
		if (u == T) return cout << c << endl, 0;
		powers[u].push_back(d);
		for (int d0 : powers[u]) {
			if (dist.find(u * MAXN + d0) == dist.end()) dist[u * MAXN + d0] = c;
			if (u - d0 >= 0 && dist.find((u - d0) * MAXN + d0) == dist.end()) {
				dist[qu[++top] = (u - d0) * MAXN + d0] = c + 1;
			}

			if (u + d0 < N && dist.find((u + d0) * MAXN + d0) == dist.end()) {
				dist[qu[++top] = (u + d0) * MAXN + 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: 0 / 43