Submission #222268

#	Time	Username	Problem	Language	Result	Execution time	Memory
222268		MODDI	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	119 ms	5744 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define IOS ios_base::sync_with_stdio(false)
using namespace std;
const int nmax=3e4+42;
priority_queue<pair<int,int> > pq;
set<int> jumps[nmax];
int wanted;
int dist[nmax];
bool in(int kade, int val){
	return jumps[kade].count(val);
}
int main()
{
	int n, m;
	cin>>n>>m;
	for(int i = 0; i < n; i++){
		dist[i] = 1e9;
	}
	for(int i = 0; i < m; i++){
		int b, p;
		cin>>b>>p;
		if(i == 0)
			dist[b] = 0, pq.push({0, b});
		if(i == 1)
			wanted = b;
			
		jumps[b].insert(p);
	}
	bool vis[n];
	memset(vis,false,sizeof(vis));
	while(!pq.empty()){
		pair<int,int> state = pq.top();
		pq.pop();
		if(vis[state.second] == false){
			vis[state.second] = true;
			int path = -state.first;
			if(state.second == wanted)
			{
				cout<<path<<endl;
				return 0;
			}
			
			for(auto jump : jumps[state.second]){
				for(int i = state.second + jump; i < n; i+=jump)
				{
					int dist_now = path + (i - state.second) / jump;
					if(dist[i] > dist_now){
						dist[i] = dist_now;
						pq.push({-dist_now,i});
					}
					if(in(i, jump))
						break;
				}
				for(int i = state.second - jump; i >= 0; i-=jump){
					int dist_now = path + (state.second -i) / jump;
					if(dist[i] > dist_now){
						dist[i] = dist_now;
						pq.push({-dist_now,i});
					}
					if(in(i, jump))
						break;
				}
			}
			
		}
	}
	cout<<-1<<endl;
	return 0;
}

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