Submission #517136

#	Time	Username	Problem	Language	Result	Execution time	Memory
517136		Drew_	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	15 ms	23412 KiB

skyscraper

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 30069;
constexpr int SQ = 180;	
constexpr unsigned short inf = 65535;

int n, m;
unsigned short cost[MAX][SQ];

unsigned short b[MAX], p[MAX];
vector<unsigned short> adj[MAX];	

int main()
{
	fastio;

	for (int i = 0; i < MAX; ++i)
		for (int j = 0; j < SQ; ++j)
			cost[i][j] = inf;

	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		cin >> b[i] >> p[i];
		adj[b[i]].pb(p[i]);
	}

	const auto valid = [&](int pos) -> bool
	{
		return 0 <= pos && pos < n;
	};

	priority_queue<array<unsigned short, 3>, vector<array<unsigned short, 3>>, greater<array<unsigned short, 3>>> pq;
	
	cost[b[0]][0] = 0;
	if (p[0] < SQ)
		cost[b[0]][p[0]] = 0;

	pq.push({0, b[0], p[0]});

	while (!pq.empty())
	{
		auto [c, pos, mov] = pq.top();
		pq.pop();

		if (cost[pos][mov] < c)
			continue;

		if (mov < SQ)
		{		
			if (cost[pos][0] > cost[pos][mov])
				cost[pos][0] = cost[pos][mov];
			if (valid(pos - mov) && cost[pos - mov][mov] > 1 + c)
				cost[pos - mov][mov] = 1 + c, pq.push({1 + c, pos - mov, mov});
			if (valid(pos + mov) && cost[pos + mov][mov] > 1 + c)
				cost[pos + mov][mov] = 1 + c, pq.push({1 + c, pos + mov, mov});
		}


		for (unsigned short x : adj[pos])
		{
			if (x < SQ)
			{
				if (valid(pos - x) && cost[pos - x][x] > 1 + c)
					cost[pos - x][x] = 1 + c, pq.push({1 + c, pos - x, x});
				if (valid(pos + x) && cost[pos + x][x] > 1 + c)
					cost[pos + x][x] = 1 + c, pq.push({1 + c, pos + x, x});
			}
			else
			{
				for (unsigned short i = pos, ctr = c; i >= 0; i -= x, ++ctr)
				{
					if (cost[i][0] > ctr)
						cost[i][0] = ctr, pq.push({ctr, i, x});
				}
				for (unsigned short i = pos, ctr = c; i < n; i += x, ++ctr)
				{
					if (cost[i][0] > ctr)
						cost[i][0] = ctr, pq.push({ctr, i, x});
				}
			}
		}
		adj[pos].clear();
	}

	// for (int i = 0; i < n; ++i)
	// 	cerr << cost[i] << " \n"[i == n-1];

	cout << (cost[b[1]][0] == inf ? -1 : cost[b[1]][0]) << '\n';

	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:69:46: warning: narrowing conversion of '(1 + ((int)c))' from 'int' to 'short unsigned int' [-Wnarrowing]
   69 |     cost[pos - mov][mov] = 1 + c, pq.push({1 + c, pos - mov, mov});
      |                                            ~~^~~
skyscraper.cpp:69:55: warning: narrowing conversion of '(((int)pos) - ((int)mov))' from 'int' to 'short unsigned int' [-Wnarrowing]
   69 |     cost[pos - mov][mov] = 1 + c, pq.push({1 + c, pos - mov, mov});
      |                                                   ~~~~^~~~~
skyscraper.cpp:71:46: warning: narrowing conversion of '(1 + ((int)c))' from 'int' to 'short unsigned int' [-Wnarrowing]
   71 |     cost[pos + mov][mov] = 1 + c, pq.push({1 + c, pos + mov, mov});
      |                                            ~~^~~
skyscraper.cpp:71:55: warning: narrowing conversion of '(((int)pos) + ((int)mov))' from 'int' to 'short unsigned int' [-Wnarrowing]
   71 |     cost[pos + mov][mov] = 1 + c, pq.push({1 + c, pos + mov, mov});
      |                                                   ~~~~^~~~~
skyscraper.cpp:80:43: warning: narrowing conversion of '(1 + ((int)c))' from 'int' to 'short unsigned int' [-Wnarrowing]
   80 |      cost[pos - x][x] = 1 + c, pq.push({1 + c, pos - x, x});
      |                                         ~~^~~
skyscraper.cpp:80:52: warning: narrowing conversion of '(((int)pos) - ((int)x))' from 'int' to 'short unsigned int' [-Wnarrowing]
   80 |      cost[pos - x][x] = 1 + c, pq.push({1 + c, pos - x, x});
      |                                                ~~~~^~~
skyscraper.cpp:82:43: warning: narrowing conversion of '(1 + ((int)c))' from 'int' to 'short unsigned int' [-Wnarrowing]
   82 |      cost[pos + x][x] = 1 + c, pq.push({1 + c, pos + x, x});
      |                                         ~~^~~
skyscraper.cpp:82:52: warning: narrowing conversion of '(((int)pos) + ((int)x))' from 'int' to 'short unsigned int' [-Wnarrowing]
   82 |      cost[pos + x][x] = 1 + c, pq.push({1 + c, pos + x, x});
      |                                                ~~~~^~~

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