Submission #441701

#	Time	Username	Problem	Language	Result	Execution time	Memory
441701		dutch	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1105 ms	260168 KiB

skyscraper

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

Compilation message (stderr)

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

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