Submission #103376

#	Time	Username	Problem	Language	Result	Execution time	Memory
103376		DystoriaX	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1069 ms	21648 KiB

skyscraper

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

int n, m;
vector<int> pos[300010];
map<int, map<int, int> > dist;

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: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: 0 / 21
• Subtask 5: 0 / 43