Submission #1113912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113912		raspy	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	95 ms	102928 KiB

skyscraper

	#include <bits/stdc++.h>
	 
	#define int long long
	#define vi vector<int>
	#define ii pair<int, int>
	#define f first
	#define s second
	#define all(x) (x).begin(), (x).end()
	#define P 31
	#define mod 1'000'000'007
	#define inf 1'000'000'000'000
	#define pb push_back
	#define str string
	#define sz(x) (x).size()
	#define vvi vector<vi>
	#define fun function
	#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
	#define file freopen("problemname.in", "r", stdin); freopen("pr.out", "w", stdout);
	#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
	 
	using namespace std;
	template <class T, int SZ> using arr = array<T, SZ>;
	 
	int b[30001];
	int power[30001];
	set<int> pravi[30001];
	set<ii> graf[30001];
	int ob[30001];
	int obp[201][30001];
	 
	void solve()
	{
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < 30001; i++)
		{
			ob[i] = inf;
			for (int j = 0; j < 201; j++)
				obp[j][i] = inf;
		}
		for (int i = 0; i < m; i++)
		{
			cin >> b[i] >> power[i];
			pravi[b[i]].insert(power[i]);
			if (power[i] > 200)
			{
				for (int j = 1; j*j <= n; j++)
				{
					if (b[i]+power[i]*j < n)
						graf[b[i]].insert({b[i]+power[i]*j, j});
					if (b[i]-power[i]*j >= 0)
						graf[b[i]].insert({b[i]-power[i]*j, j});
				}
			}
		}
		priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
		if (power[0] > 200)
		{
			pq.push({0, b[0], -1});
			ob[b[0]] = 0;
		}
		else
		{
			pq.push({0, b[0], power[0]});
			obp[b[0]][power[0]] = 0;
		}
		while (pq.size())
		{
			auto [d, pos, pow] = pq.top();
			pq.pop();
			if (pos == b[1])
			{
				cout << d << "\n";
				return;
			}
			if (pow > 200)
			{
				if (ob[pos] < d) continue;
				for (auto [p, w] : graf[pos])
				{
					if (ob[p] > d+w)
					{
						ob[p] = d+w;
						pq.push({d+w, p, pow});
					}
				}
				for (int p : pravi[pos])
				{
					if (obp[pos][p] > d)
					{
						obp[pos][p] = d;
						pq.push({d, pos, p});
					}
				}
			}
			else
			{
				if (obp[pow][pos] < d) continue;
				if (pos-pow >= 0 && obp[pow][pos-pow] > d+1)
				{
					obp[pow][pos-pow] = d+1;
					pq.push({d+1, pos-pow, pow});
				}
				if (pos+pow < n && obp[pow][pos+pow] > d+1)
				{
					obp[pow][pos+pow] = d+1;
					pq.push({d+1, pos+pow, pow});
				}
				if (ob[pos] == 0)
				{
					ob[pos] = d;
					pq.push({d, pos, -1});
				}
				for (int p : pravi[pos])
				{
					if (obp[p][pos] > d)
					{
						obp[p][pos] = d;
						pq.push({d, pos, p});
					}
				}
			}
		}
		cout << -1 << "\n";
	}
	 
	signed main()
	{
		oopt;
		int t = 1;
		// cin >> t;
		while (t--)
			solve();
		return 0;
	}

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