Submission #1033115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033115		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	644 ms	8408 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

vector<int> g[200005];

int d[200005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	
	cin >> n >> m;
	
	int s, t;
	
	for (int i = 1; i <= m; ++i) {
		int b, p;
		
		cin >> b >> p;
		
		b++;
		
		if (i == 1) {
			s = b;
		} else if (i == 2) {
			t = b;
		}
		
		g[b].emplace_back(p);
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	
	memset(d, 0x3f, sizeof d);
	
	d[s] = 0;
	
	q.emplace(d[s], s);
	
	int ans = -1;
	
	while (q.size()) {
		int u = q.top().second, dl = q.top().first;
		
		q.pop();
		
		if (dl > d[u]) {
			continue;
		}
		
		if (u == t) {
			ans = dl;
			break;
		}
		
		for (int i: g[u]) {
			
			for (int j = 1; u + j * i <= n; ++j) {
				int v = u + j * i;
				
				if (d[v] > d[u] + j) {
					d[v] = d[u] + j;
					q.emplace(d[v], v);
				}
			}
			
			for (int j = 1; u - j * i >= 1; ++j) {
				int v = u - j * i;
				
				if (d[v] > d[u] + j) {
					d[v] = d[u] + j;
					q.emplace(d[v], v);
				}
				
			}
				
		}
	}
	
	cout << ans << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:54:3: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (u == t) {
      |   ^~

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