제출 #30888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30888		Navick	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1000 ms	33116 KiB

skyscraper

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3e4 + 10, M = 5e6, INF = 1e9;
map<pii, int> d;
vector<int> t[N];
bool vis[N];
deque<pii> q;

int main(){
	int n, m; cin >> n >> m;
	int sp, sb, se;

	for(int i=0; i<m; i++){
		int p, b; cin >> p >> b;
		t[p].pb(b);
		if(i == 0)
			sp = p, sb = b;
		if(i == 1)
			se = p;
	}

	q.push_back({sp, sb});
	d[{sp, sb}] = 0;

	while(!q.empty()){
		int p = q.front().F, b = q.front().S;
		int dis = d[{p, b}];
		q.pop_front();
		if(!vis[p]){
			for(auto l : t[p]){
				if(d.count({p, l}) == 0)
					d[{p, l}] = dis, q.push_front({p, l});
			}
			vis[p] = true;
		}
		if(p + b < n){
			if(d.count({p + b, b}) == 0)
				d[{p + b, b}] = dis + 1, q.push_back({p + b, b});
		}
		if(p - b >= 0){
			if(d.count({p - b, b}) == 0)
				d[{p - b, b}] = dis + 1, q.push_back({p - b, b});
		}
	}
	int mn = INF;
	for(int i=0; i<=n; i++){
		if(d.count({se, i}))
			mn = min(mn, d[{se, i}]);
	}
	if(mn < INF)
		cout << mn << endl;
	else cout << -1 << endl;
}

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