Submission #498047

#	Time	Username	Problem	Language	Result	Execution time	Memory
498047		the_visitor2341	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	2640 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;


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});
			}
		}
	}
	cout << d[en] << "\n";
}

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

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