Submission #282290

#	Time	Username	Problem	Language	Result	Execution time	Memory
282290		peijar	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	972 ms	25984 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 = 175;

int nbSauts[MAX][SQRT+1];

struct Situation
{
	int building, power, sauts;

	bool operator<(Situation other) const
	{
		return sauts > other.sauts;
	}
};

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);
	set<int> dogsInBat[MAX];
	for (auto &[bat, pow] : dogs)
	{
		cin >> bat >> pow;
		dogsInBat[bat].insert(pow);
	}
	
	for (int i(0); i < nbBat; ++i)
		for (int j(0); j <= SQRT; ++j)
			nbSauts[i][j] = 1e9;
	nbSauts[dogs[0].first][SQRT] = 0;

	priority_queue<Situation> q;
	q.push({dogs[0].first, SQRT, 0});
	while (SZ(q))
	{
		auto situ = q.top(); q.pop();

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

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