Submission #402998

#	Time	Username	Problem	Language	Result	Execution time	Memory
402998		yoavL	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1103 ms	243536 KiB

skyscraper

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

#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 = 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 = 1e9;

ll n, m;
vvll d, have; // [place][sky ind]
vll s, p;
vvb vis;

void bfs()
{
	deque<pll> q; // {place, sky ind}
	q.push_front({ 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_front();
		if (vis[b][ind]) continue;
		vis[b][ind] = true;
		rep(i, have[b].size()) {
			if (d[b][have[b][i]] != inf) continue;
			d[b][have[b][i]] = d[b][ind];
			q.push_front({ b, have[b][i] });
		}
		have[b].clear();

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


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

}

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);
	}

	d.resize(n, vll(m, inf));
	vis.resize(n, vb(m, 0));
	bfs();
	ll ans = d[s[1]][1];
	if (ans == inf) ans = -1;
	pr(ans);
}

/*

5 3
0 2
1 1
4 1


*/

Compilation message (stderr)

skyscraper.cpp:11: warning: "rep" redefined
   11 | #define rep(i, e) for(ll i = 0; i < e; i++)
      | 
skyscraper.cpp:10: note: this is the location of the previous definition
   10 | #define rep(i, s, e) for(ll i = s; i < e; i++)
      | 
skyscraper.cpp: In function 'void bfs()':
skyscraper.cpp:11:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define rep(i, e) for(ll i = 0; i < e; i++)
......
   45 |   rep(i, have[b].size()) {
      |       ~~~~~~~~~~~~~~~~~            
skyscraper.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(i, have[b].size()) {
      |   ^~~

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