제출 #282261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282261		peijar	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	3 ms	1696 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAX = 3e4;
const int SQRT = 200;

int nbSauts[MAX][SQRT+1];

struct Situation
{
	int building, power;

	int get(void)
	{
		return nbSauts[building][power];
	}
};

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbBat, nbDog;
	cin >> nbBat >> nbDog;

	vector<pair<int, int> > dogs(nbDog);
	vector<int> dogsInBat[MAX];
	for (auto &[bat, pow] : dogs)
	{
		cin >> bat >> pow;
		dogsInBat[bat].push_back(pow);
	}
	
	for (int i(0); i < nbBat; ++i)
		for (int j(0); j <= SQRT; ++j)
			nbSauts[i][j] = 1e9;
	nbSauts[dogs[0].first][dogs[0].second] = 0;

	queue<Situation> q;
	q.push({dogs[0].first, dogs[0].second});
	while (SZ(q))
	{
		auto situ = q.front(); q.pop();

		if (situ.building == dogs[1].first)
		{
			cout << situ.get() << endl;
			return 0;
		}
		for (auto p : dogsInBat[situ.building])
		{
			if (p < SQRT)
			{
				if (situ.building - p >= 0 and nbSauts[situ.building-p][p] == 1e9)
				{
					q.push({situ.building-p, p});
					nbSauts[situ.building-p][p] = situ.get() + 1;
				}
				if (situ.building+p < nbBat and nbSauts[situ.building+p][p] == 1e9)
				{
					q.push({situ.building+p, p});
					nbSauts[situ.building+p][p] = situ.get() + 1;
				}
			}
			else
			{
				for (int i(1); p * i + situ.building < nbBat; ++i)
				{
					if (nbSauts[situ.building+i*p][SQRT] == 1e9)
					{
						q.push({situ.building+i*p, SQRT});
						nbSauts[situ.building+i*p][SQRT] = situ.get() + 1;
					}
				}
				for (int i(-1); p*i + situ.building >= 0; --i)
				{
					if (nbSauts[situ.building+i*p][SQRT] == 1e9)
					{
						q.push({situ.building+i*p, SQRT});
						nbSauts[situ.building+i*p][SQRT] = situ.get() + 1;
					}
				}
			}
		}
		if (situ.power < SQRT)
		{
			int p = situ.power;
			if (situ.building - p >= 0 and nbSauts[situ.building-p][p] == 1e9)
			{
				q.push({situ.building-p, p});
				nbSauts[situ.building-p][p] = situ.get() + 1;
			}
			if (situ.building+p < nbBat and nbSauts[situ.building+p][p] == 1e9)
			{
				q.push({situ.building+p, p});
				nbSauts[situ.building+p][p] = situ.get() + 1;
			}
		}
	}
	cout << -1 << endl;
}

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