Submission #874605

#	Time	Username	Problem	Language	Result	Execution time	Memory
874605		h4d1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1032 ms	1116 KiB

skyscraper

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

const int inf = 2e9;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	pair<int, int> a[m];
	for(int i = 0; i < m; i++)
	{
		cin >> a[i].first >> a[i].second;
	}
	int s = a[0].first, t = a[1].first, adj[n];
	fill(adj, adj+n, m);
	sort(a, a+m);
	for(int i = 0; i < m; i++)
	{
		if(!i)
		{
			adj[a[i].first] = i;
		}
		else if(a[i].first != a[i-1].first)
		{
			adj[a[i].first] = i;
		}
	}

	int d[n];
	fill(d, d+n, inf);
	priority_queue<pair<int, int>> pq;
	pq.push({d[s]=0, s});
	while(pq.size())
	{
		int v = pq.top().second;
		pq.pop();
		for(int i = adj[v]; ((i < m)&&(a[i].first == v)); i++)
		{
			int j = a[i].second, x = 0;
			while((v+(x*j) < n) || (v-(x*j) >= 0))
			{
				if((v+(x*j) < n) && (d[v+(x*j)] > d[v]+x))
				{
					pq.push({d[v+(x*j)] = d[v]+x, v+(x*j)});
				}
				if((v-(x*j) >= 0) && (d[v-(x*j)] > d[v]+x))
				{
					pq.push({d[v-(x*j)] = d[v]+x, v-(x*j)});
				}
				x++;
			}
		}
	}
	if(d[t] != inf)
	{
		cout << d[t] << '\n';
	}
	else
	{
		cout << "-1\n";
	}
}

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