제출 #569017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569017		Alan	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	222 ms	20816 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> adj[30000];

struct node {
	int u, di, vel;
};

int main() {
	unordered_map<ll, bool> vis;
	int n, m, b, p, d0, d1;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> b >> p;
		if (i == 0) d0 = b;
		if (i == 1) d1 = b;
		if (0 <= b+p && b+p < n) adj[b].push_back(p);
		if (0 <= b-p && b-p < n) adj[b].push_back(-p);
	}
	queue<node> bfs;
	bfs.push({d0, 0, 0});
	while (!bfs.empty()) {
		auto& [u, di, vel] = bfs.front();
		if (u == d1) {
			cout << di << "\n";
			return 0;
		}
		bfs.pop();
		if (!vis[(u<<16)+vel] && u+vel >= 0 && u+vel < n) bfs.push({u+vel, di+1, vel}), vis[(u<<16)+vel] = true;
		for (auto& s : adj[u]) if (!vis[(u<<16)+s]) bfs.push({u+s, di+1, s}), vis[(u<<16)+s] = true;
	}
	cout << "-1\n";
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:3: warning: 'd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |   if (u == d1) {
      |   ^~
skyscraper.cpp:23:10: warning: 'd0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |  bfs.push({d0, 0, 0});
      |  ~~~~~~~~^~~~~~~~~~~~

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