Submission #403056

#	Time	Username	Problem	Language	Result	Execution time	Memory
403056		yoavL	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1071 ms	118208 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

#define upmax(a, b) a = max(a, b);
#define upmin(a, b) a = min(a, b);
#define pr(x) cout << x << endl;
#define wpr(x) cout << #x << ": " << x << endl;
#define rep(i, s, e) for(ll i = s; i < e; i++)
#define rep(i, e) for(ll i = 0; i < e; i++)

using namespace std;

using ll = unsigned short int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pll = pair<ll, ll>;

const ll inf = 5e4;
const ll maxn = 2002;
const ll maxm = 30002;
ll n, m;
//vvll d, have; // [place][sky ind]
//vvll have;
vll have[maxn];
ll d[maxn][maxm];

ll s[maxm], p[maxm];
//vll s, p;
//vb vis;
bool vis[maxn];

queue<pll> q; // {place, sky ind}


inline void make(ll b, ll ind)
{
	ll jump = p[ind];
	if (b - jump >= 0 && d[b - jump][ind] == inf) {
		d[b - jump][ind] = d[b][ind] + 1;
		q.push({ b - jump, ind });
	}



	if (b + jump < n && d[b + jump][ind] == inf) {
		d[b + jump][ind] = d[b][ind] + 1;
		q.push({ b + jump, ind });
	}
}


inline void bfs()
{
	q.push({ s[0], 0 });
	d[s[0]][0] = 0;

	while (!q.empty()) {
		ll b = q.front().first;
		ll ind = q.front().second;
		//wpr(b);
		//wpr(ind);
		//cout << "dist: " << d[b][ind] << endl;
		q.pop();
		if (!vis[b]) {
			rep(i, have[b].size()) {
				//if (d[b][have[b][i]] != inf) continue;
				if (d[b][have[b][i]] == inf) d[b][have[b][i]] = d[b][ind];
				else continue;
				//q.push({ b, have[b][i] });
				make(b, have[b][i]);
				
			}
			vis[b] = true;
		}
		make(b, ind);
		//make()
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	//s.resize(m);
	//p.resize(m);
	//have.resize(n);
	rep(i, m) {
		cin >> s[i] >> p[i];
		have[s[i]].push_back(i);
	}

	
	for (ll i = 0; i < n; i++) {
		vis[i] = false;
		for (ll j = 0; j < m; j++) {
			d[i][j] = inf;
		}
	}

	//d.resize(n, vll(m, inf));
	//vis.resize(n, false);
	bfs();
	ll ans = d[s[1]][1];
	if (ans == inf) {
		pr("-1");
	}
	else pr(ans);
}

/*

5 3
0 2
1 1
4 1


*/

Compilation message (stderr)

skyscraper.cpp:12: warning: "rep" redefined
   12 | #define rep(i, e) for(ll i = 0; i < e; i++)
      | 
skyscraper.cpp:11: note: this is the location of the previous definition
   11 | #define rep(i, s, e) for(ll i = s; i < e; i++)
      |

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