제출 #403044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403044		yoavL	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1097 ms	118252 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;

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

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


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


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

	

	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


*/

컴파일 시 표준 에러 (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