Submission #1256153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256153		namhh	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	121 ms	25784 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 || (v < block && check[u][v] == 0)){
				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});
					}
					if(v < block){
						if(check[i][v] == 1) break;
						check[i][v] = 1;
					}
				}
				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(v < block){
						if(check[i][v] == 1) break;
						check[i][v] = 1;
					}
				}
			}
		}
	}
	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]);
	}
	for(int i = 0; i < n; i++){
		sort(adj[i].begin(),adj[i].end());
		adj[i].erase(unique(adj[i].begin(),adj[i].end()),adj[i].end());
	}
	dijkstra();
}

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