제출 #1275851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275851		ehsan1011000	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	613 ms	9312 KiB

skyscraper

#include <bits/stdc++.h>
#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];
pq vals;

void dijk(int st){
	dist[st] = 0;
	vals.push({0, st});
	while(! vals.empty()){
		auto [d, v] = vals.top();
		vals.pop();
		if(d > dist[v]) continue;
		if(v == b[1]) break;
		for(int x : e[v]){
			int step = 0;
			for(int i = v + x; i < n; i += x){
				step ++;
				if(dist[v] + step >= dist[i]) continue;
				dist[i] = dist[v] + step;
				vals.push({dist[i], i});
			}
			step = 0;
			for(int i = v - x; i >= 0; i -= x){
				step ++;
				if(dist[v] + step >= dist[i]) continue;
				dist[i] = dist[v] + step;
				vals.push({dist[i], i});
			}
		}
	}
}

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: 43 / 43