제출 #498052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498052		the_visitor2341	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	225 ms	124012 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define sz(v) (int)(v).size()
#define all(v) begin(v),end(v)
#define each(e,v) for(auto &e:(v))
#define pb push_back
#define f first
#define s second

typedef long long ll;

const ll INF = 1e18;


template<class T> bool ckmin(T&a, const T&b) {
	return b < a ? a = b, 1 : 0;
}

const int MX = 3e4+5;
int N,M, st,p,en;
set<int> jmp[MX];
vector<pair<ll,int>> g[MX];
ll d[MX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

void solve() {
	cin>>N>>M;
	cin>>st>>p;
	jmp[st].insert(p);
	cin>>en>>p;
	FOR(i,2,M) {
		int b;
		cin>>b>>p;
		jmp[b].insert(p);
	}
	F0R(i,N) {
		each(p,jmp[i]) {
			for(int j = 1; ; j++) {
				int pos = i+j*p;
				if(pos<0 || pos>=N) break;
				g[i].pb({pos,j});
				if(jmp[pos].count(p)) break;
			}
		}
	}
	F0R(i,N) {
		each(p,jmp[i]) {
			for(int j = 1;; j++) {
				int pos = i-j*p;
				if(pos<0 || pos>=N) break;
				g[i].pb({pos,j});
				if(jmp[pos].count(p)) break;
			}
		}
	}
	memset(d,0x3f,sizeof d);
	pq.push({d[st] = 0, st});
	while(sz(pq)) {
		int u = pq.top().s; ll du = pq.top().f;
		pq.pop();
		if(du > d[u]) continue;
		F0R(i,sz(g[u])) {
			int v = g[u][i].f; ll dv = du + g[u][i].s;
			if(ckmin(d[v],dv)) {
				pq.push({d[v],v});
			}
		}
	}
	if(d[en] >= INF) {
		cout << "-1\n";
	}
	else cout << d[en] << "\n";
}

int main() {
	int t=1;
	//cin>>t;
	while(t-->0) solve();
}

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