Submission #1275772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275772		ehsan1011000	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1096 ms	2124 KiB

skyscraper

#include <bits/stdc++.h>
#include <iomanip>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,sse4")
 
using namespace std;
 
# define pb push_back
# define pf push_front
# define ff first
# define ss second
# define ll long long
# define lc id * 2
# define rc lc | 1
//# define int long long
# define mid (r + l) / 2
//# define mp make_pair
typedef long double ld;
#define kill(x)  cout << x << '\n', exit(0)
typedef pair<int, char> pic;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 3e4 + 10, maxm = 4e5 + 10, sq = 1300, LOG = 30, mod = 1e9 + 7;
const ll inf = 1e17;
int n, m;
int p[maxn], b[maxn];
vector<int> e[maxn];
ll dist[maxn];
bool mark[maxn];

void dijk(int st){
	dist[st] = 0;
	while(true){
		int v = -1;
		ll mn = inf;
		for(int i = 0; i < n; i ++){
			if(mark[i]) continue;
			if(dist[i] < mn){
				mn = dist[i];
				v = i;
			}
		}
		if(v < 0 || v == b[1]) break;
		mark[v] = 1;
		for(int d : e[v]){
			for(int i = v + d; i < n; i += d){
				int step = (i - v) / d;
				dist[i] = min(dist[i], dist[v] + step);
			}
			for(int i = v - d; i >= 0; i -= d){
				int step = (v - i) / d;
				dist[i] = min(dist[i], dist[v] + step);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i ++){
		cin >> b[i] >> p[i];
		e[b[i]].pb(p[i]);
	}
	for(int i = 0; i < n; i ++){
		sort(e[i].begin(), e[i].end());
		e[i].resize(unique(e[i].begin(), e[i].end()) - e[i].begin());
	}
	memset(dist, 63, sizeof(dist));
	dijk(b[0]);
	cout << (dist[b[1]] >= inf ? -1 : dist[b[1]]) << '\n';
    return 0; 
}

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