Submission #319534

#	Time	Username	Problem	Language	Result	Execution time	Memory
319534		TeaTime	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1086 ms	48024 KiB

skyscraper

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 30002, INF = 1e9 + 10;

ll n, m;
set<pair<ll, ll>> us;

ll dist[SZ];
bool used[SZ];

vector<ll> cur[SZ];
int main()
{
	fastInp;

	cin >> n >> m;
	ll ind = 0, ind2 = 0, b2 = 0;

	for (int i = 0; i < m; i++) {
		ll b, p;
		cin >> b >> p;
		
		cur[b].push_back(p);
		if (i == 0) {
			ind2 = b;
			b2 = p;
		}
		if (i == 1) {
			ind = b;
		}
	}

	queue<pair<ll, ll>> q;
	queue<ll> q2;
	
	q.push({ ind2, b2 });

	for (int i = 0; i < n; i++) dist[i] = INF;
	dist[ind2] = 0;
	q2.push(0);
	swap(n, m);
	while (!q.empty()) {
		ll v = q.front().first;
		pair<ll, ll> u = q.front();
		ll d = q2.front();
		q2.pop();
		q.pop();
		ll c = u.second;
		if (us.find({ v - c, c }) == us.end()) {
			if (v - c >= 0 && v - c < m) {
				us.insert({ v - c, c });
				dist[v - c] = min(dist[v - c], d + 1);
				q.push({ v - c, c });
				q2.push({ d + 1 });
			}
		}

		if (us.find({ v + c, c }) == us.end()) {
			if (v + c >= 0 && v + c < m) {
				us.insert({ v + c, c });
				dist[v + c] = min(dist[v + c], d + 1);
				q.push({ v + c, c });
				q2.push({ d + 1 });
			}
		}

		if (!used[v]) {
			used[v] = 1;
			for (auto c : cur[v]) {
				if (us.find({ v - c, c }) == us.end()) {
					if (v - c >= 0 && v - c < m) {
						us.insert({ v - c, c });
						dist[v - c] = min(dist[v - c], d + 1);
						q.push({ v - c, c });
						q2.push({ d + 1 });
					}
				}

				if (us.find({ v + c, c }) == us.end()) {
					if (v + c >= 0 && v + c < m) {
						us.insert({ v + c, c });
						dist[v + c] = min(dist[v + c], d + 1);
						q.push({ v + c, c });
						q2.push({ d + 1 });
					}
				}
			}
		}

		if (dist[ind] != INF) {
			cout << dist[ind];
			return 0;
		}
	}

	cout << "-1";
	return 0;
}

/*
5
1 4 1 3 5
2 1 4 1 2
5 1 1 4 5
3 5 1 1 2
4 3 5 1 1

3
1 1 1
2 2 2
3 3 3
*/

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