Submission #441700

#	Time	Username	Problem	Language	Result	Execution time	Memory
441700		dutch	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	161 ms	73184 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 3e4, INF = 2e9;
vector<array<int, 2>> g[MAXN*2];
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, b, p; cin >> n >> m;
 
	int s, t;
	for(int j=0; j<m; ++j){
		cin >> b >> p;
		if(j == 0) s = b;
		if(j == 1) t = b;
		if(p == 1){
			g[b+b].push_back({b+b+p, 0});
		}else{
			for(int i=b%p; i<n; i+=p) g[b+b].push_back({i*2, abs(b-i)/p});
		}
	}
 
	for(int i=0; i<n; ++i){
		int u = i * 2;
		g[u+1].push_back({u, 0});
		if(i-1 >= 0) g[u+1].push_back({u-1, 1});
		if(i+1 <  n) g[u+1].push_back({u+3, 1});
	}
 
	priority_queue<array<int, 2>> q;
	int d[n*2]; fill(d, d+n+n, INF);
	q.push({d[s+s] = 0, s+s});
 
	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])
			if(d[v] > dist + w) q.push({-(d[v] = dist + w), v});
	}
 
	if(d[t+t] == INF) d[t+t] = -1;
	cout << d[t+t];
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32:13: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |  q.push({d[s+s] = 0, s+s});
      |            ~^~
skyscraper.cpp:42:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |  if(d[t+t] == INF) d[t+t] = -1;
      |       ~^~

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