제출 #30892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30892		Navick	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1000 ms	121436 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;
unordered_map<int, int> d;
vector<int> t[N];
bool vis[N];
deque<pii> q;
int sp, sb, se;


inline ll gg(ll a, ll b){
	return a * N + b;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;

	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[gg(sp, sb)] = 0;

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

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:73:12: warning: division by zero [-Wdiv-by-zero]
   cout << 1/0 << endl;
            ^

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