Submission #441712

#	Time	Username	Problem	Language	Result	Execution time	Memory
441712		dutch	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	87 ms	4928 KiB

skyscraper

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#define DIJKSTRA if(d[v] > dist + w) q.push({-(d[v] = dist + w), v})
 
const int SQRT = 2, MAXN = 3e4, INF = 2e9;
vector<array<int, 2>> g[MAXN*SQRT];
vector<int> h[MAXN];
int n, m, b, p, s, t, d[MAXN*SQRT];
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
 
	for(int _=0; _<m; ++_){
		cin >> b >> p;
		if(_ == 0) s = b;
		if(_ == 1) t = b;
		int c = b * SQRT;
		if(p < SQRT) g[c].push_back({c+p, 0});
		else h[b].push_back(p);
	}
 
	priority_queue<array<int, 2>> q;
	fill(d, d+n*SQRT, INF);
	q.push({d[s*SQRT] = 0, s*SQRT});
 
	while(!q.empty()){
		int u = q.top()[1], dist = -q.top()[0];
		q.pop();
		if(dist != d[u]) continue;
		for(auto &[v, w] : g[u]) DIJKSTRA;
 
		int j = u % SQRT, v = u - j, w = 0;
		DIJKSTRA;
 
		for(int x : {-1, 1}){
			v = u+ x * j * SQRT, w = 1;
			if(0<=v && v<n*SQRT) DIJKSTRA;
		}
 
		if(j) continue;
		b = u / SQRT;
		for(int &k : h[b]) for(int i=b%k; i<n; i+=k){
			v = i*SQRT, w = abs(b-i)/k;
			DIJKSTRA;
		}
	}
 
	if(d[t*SQRT] == INF) d[t*SQRT] = -1;
	cout << d[t*SQRT];
}

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