Submission #81829

#	Time	Username	Problem	Language	Result	Execution time	Memory
81829		antimirage	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1062 ms	12204 KiB

skyscraper

#include <bits/stdc++.h>

#define mk make_pair
#define pb push_back
#define fr first
#define sc second

using namespace std;

const int N = 3e4 + 5;

int n, m, en, pos, p, d[N], st;

set <int> vec[N];

priority_queue < pair <int, int> > q;

int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &pos, &p);
		vec[pos].insert(p);
		if (i == 1)
			st = pos;
		if (i == 2)
			en = pos;
	}
	memset(d, 0x3f3f3f3f, sizeof(d));
	d[st] = 0;
	q.push( mk( 0, st ) );
	
	while (!q.empty())
	{
		int v = q.top().sc, len = -q.top().fr;
		q.pop();
		if (d[v] < len) continue;
		
		for (auto to : vec[v])
		{
			for (int i = v % to; i < n; i += to)
			{
				if (d[i] > d[v] + abs(v - i) / to)
				{
					d[i] = d[v] + abs(v - i) / to;
					q.push( mk( -d[i], i ) );
				}
			}
		}
	}
	if (d[en] > 1e9)
		d[en] = -1;
	cout << d[en] << endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &pos, &p);
   ~~~~~^~~~~~~~~~~~~~~~~~

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