Submission #1256143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256143		namhh	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1096 ms	16364 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e4+5;
const int block = 170;
int n,m,check[N][block],a[N],w[N],d[N];
vector<int>adj[N];
void dijkstra(){
	for(int i = 0; i < n; i++) d[i] = 1e9;
	d[a[0]] = 0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,a[0]});
	while(!pq.empty()){
		auto[c,u] = pq.top();
		pq.pop();
		if(c > d[u]) continue;
		for(int v: adj[u]){
			if(v >= block || !check[u][v]){
				if(v < block) check[u][v] = 1;
				for(int i = u+v; i < n; i += v){
					if(d[i] > d[u]+(i-u)/v){
						d[i] = d[u]+(i-u)/v;
						pq.push({d[i],i});
					}
				}
				for(int i = u-v; i >= 0; i -= v){
					if(d[i] > d[u]+(u-i)/v){
						d[i] = d[u]+(u-i)/v;
						pq.push({d[i],i});
					}
				}
			}
		}
	}
	if(d[a[1]] > 9e8) cout << -1;
	else cout << d[a[1]];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		cin >> a[i] >> w[i];
		adj[a[i]].push_back(w[i]);
	}
	dijkstra();
}

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