oj.uz

답안 #403004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403004 2021-05-12T16:13:52 Z yoavL Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 1 ms 312 KB 
#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;

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]) {
			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] });
			}
			vis[b] = true;
		}
		
		//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, false);
	bfs();
	ll ans = d[s[1]][1];
	if (ans == inf) ans = -1;
	pr(ans);
}

/*

5 3
0 2
1 1
4 1


*/

Compilation message

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -