Submission #874609

#	Time	Username	Problem	Language	Result	Execution time	Memory
874609		h4d1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1070 ms	940 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;
	scanf("%d%d", &n, &m);
	pair<int, int> a[m];
	for(int i = 0; i < m; i++)
	{
		scanf("%d%d", &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++;
			}
		}
	}
	printf("%d\n", d[t] != 2e9 ? d[t] : -1);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d%d", &a[i].first, &a[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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