Submission #1150192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150192		zhasyn	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	1096 KiB

skyscraper

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 3 * 1e4 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
	return (1LL * a * b % mod + mod) % mod;
}
ll x[N], p[N], d[N];
vector <pll> q[N];
int main(){
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	ll n, m;
  	cin >> n >> m;
  	for(ll i = 0; i < m; i++){
  		cin >> x[i] >> p[i];
  	}
  	for(ll i = 0; i < m; i++){
  		for(ll j = x[i] + p[i];; j += p[i]){
  			if(j >= n) break;
  			//cout << j << " ";
  			q[x[i]].pb({j, (j - x[i])/p[i]});
  		}
  		//cout << endl;
  		for(ll j = x[i] - p[i];; j -= p[i]){
  			if(j < 0) break;
  			q[x[i]].pb({j, (x[i] - j)/p[i]});
  		}
  	}
  	for(ll i = 0; i < n; i++){
  		d[i] = LLONG_MAX;
  	}
  	d[0] = 0;
  	set <pll> st;
  	st.insert({d[0], 0});
  	while((ll)st.size() != 0){
		ll v = st.begin()->S;
  		st.erase(st.begin());
  		for(auto u : q[v]){
  			if(d[u.F] > d[v] + u.S){
  				st.erase({d[u.F], u.F});
  				d[u.F] = d[v] + u.S;
  				st.insert({d[u.F], u.F});
  			}
  		}
  	}
  	if(d[1] ==LLONG_MAX) cout << -1;
  	else cout << d[1];
  	
  return 0;
}

 

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