Submission #104380

#	Time	Username	Problem	Language	Result	Execution time	Memory
104380		DystoriaX	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	64 ms	23524 KiB

skyscraper

#include <bits/stdc++.h>
 
#define pb push_back
 
using namespace std;
 
int n, m;
vector<int> pos[300010];
int dist[2010][2010];
 
int main(){
	scanf("%d%d", &n, &m);
 
	int stb, stp, en;
	for(int i = 0; i < m; i++){
		int b, p;
		scanf("%d%d", &b, &p);
 
		if(i == 0) stb = b, stp = p;
		if(i == 1) en = b;
 
		pos[b].pb(p);
	}
 
	queue<pair<int, int> > q;
	q.push({stb, stp});
	dist[stb][stp] = 1;
 
	int ans = -1;
	while(!q.empty()){
		int b, p;
		tie(b, p) = q.front(); q.pop();
 
		if(b == en){
			ans = dist[b][p] - 1;
			break;
		}
 
		//cout << b << " " << p << " " << dist[b][p] << endl;
		if(b + p < n && dist[b + p][p] == 0){
			dist[b + p][p] = dist[b][p] + 1;
			q.push({b + p, p});
		}
		if(b - p >= 0 && dist[b - p][p] == 0){
			dist[b - p][p] = dist[b][p] + 1;
			q.push({b - p, p});
		}
 
		for(auto v : pos[b]){
			if(b + v < n && dist[b + v][v] == 0){
				dist[b + v][v] = dist[b][p] + 1;
				q.push({b + v, v});
			}
			if(b - v >= 0 && dist[b - v][v] == 0){
				dist[b - v][v] = dist[b][p] + 1;
				q.push({b - v, v});
			}
		}
	}
 
	printf("%d\n", ans);
 
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &b, &p);
   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:27:17: warning: 'stp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dist[stb][stp] = 1;
  ~~~~~~~~~~~~~~~^~~
skyscraper.cpp:27:17: warning: 'stb' may be used uninitialized in this function [-Wmaybe-uninitialized]
skyscraper.cpp:34:3: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(b == en){
   ^~

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