oj.uz

답안 #1023431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023431 2024-07-14T18:43:40 Z xnqs Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 202 ms 46512 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>

int x, dog_cnt;
std::vector<std::pair<int,int>> dogs; 
std::unordered_map<int,int> dist[30005];
std::vector<int> dogs_in[30005];

int astar(int pos, int dog) {
	std::priority_queue<std::tuple<int,int,int>, std::vector<std::tuple<int,int,int>>, std::greater<std::tuple<int,int,int>>> pq;
	pq.emplace(0+std::abs(pos-dogs[1].first),pos,dog);
	dist[pos][dog] = 0;

	int iterations = 1000000;
	while (!pq.empty()&&iterations--) {
		auto [c, pos, dog] = pq.top();
		pq.pop();

		if (pos-dogs[dog].second>=0) {
			if (!dist[pos-dogs[dog].second].count(dog)||dist[pos-dogs[dog].second][dog]>dist[pos][dog]+1) {
				dist[pos-dogs[dog].second][dog] = dist[pos][dog]+1;
				pq.emplace(dist[pos-dogs[dog].second][dog]+std::abs((pos-dogs[dog].second)-dogs[1].first),
				          pos-dogs[dog].second,
						  dog);
			}
		}
		if (pos+dogs[dog].second<x) {
			if (!dist[pos+dogs[dog].second].count(dog)||dist[pos+dogs[dog].second][dog]>dist[pos][dog]+1) {
				dist[pos+dogs[dog].second][dog] = dist[pos][dog]+1;
				pq.emplace(dist[pos+dogs[dog].second][dog]+std::abs((pos+dogs[dog].second)-dogs[1].first),
				          pos+dogs[dog].second,
						  dog);
			}
		}

		for (const auto& i : dogs_in[pos]) {
			if (!dist[pos].count(i)||dist[pos][i]>dist[pos][dog]) {
				dist[pos][i] = dist[pos][dog];
				pq.emplace(dist[pos][i]+std::abs(pos-dogs[1].first),
				          pos,
						  i);
			}
		}
	}

	int min = 0x3f3f3f3f;
	for (int i = 0; i < dog_cnt; i++) {
		if (!dist[dogs[1].first].count(i)) {
			continue;
		}

		min = std::min(min, dist[dogs[1].first][i]);
	}

	return ((min==0x3f3f3f3f) ? -1 : min);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> dog_cnt;
	dogs.reserve(dog_cnt);

	for (int i = 0, a, b; i < dog_cnt; i++) {
		std::cin >> a >> b;
		dogs.emplace_back(a,b);
		dogs_in[a].emplace_back(i);
	}

	std::cout << astar(dogs[0].first, 0) << "\n";
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2680 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2736 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 9 ms 3104 KB Output is correct
12 Correct 76 ms 10940 KB Output is correct
13 Correct 72 ms 10832 KB Output is correct
14 Correct 9 ms 3160 KB Output is correct
15 Correct 7 ms 2908 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 10 ms 3084 KB Output is correct
12 Correct 69 ms 10712 KB Output is correct
13 Correct 73 ms 10832 KB Output is correct
14 Correct 9 ms 3160 KB Output is correct
15 Correct 8 ms 2908 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 25 ms 3676 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Incorrect 188 ms 46464 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2804 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 8 ms 3072 KB Output is correct
12 Correct 72 ms 10788 KB Output is correct
13 Correct 75 ms 10836 KB Output is correct
14 Correct 9 ms 3160 KB Output is correct
15 Correct 7 ms 2904 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 22 ms 3716 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Incorrect 183 ms 46368 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 3 ms 2812 KB Output is correct
11 Correct 10 ms 3160 KB Output is correct
12 Correct 92 ms 10788 KB Output is correct
13 Correct 71 ms 10892 KB Output is correct
14 Correct 9 ms 3160 KB Output is correct
15 Correct 7 ms 2904 KB Output is correct
16 Correct 1 ms 2832 KB Output is correct
17 Correct 22 ms 3676 KB Output is correct
18 Correct 2 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Incorrect 202 ms 46512 KB Output isn't correct
21 Halted 0 ms 0 KB -