oj.uz

Submission #1023438

# Submission time Handle Problem Language Result Execution time Memory
1023438 2024-07-14T18:47:46 Z xnqs Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 294 ms 84564 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 = 1900000;
	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2736 KB Output is correct
4 Correct 2 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 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 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 2652 KB Output is correct
11 Correct 7 ms 3164 KB Output is correct
12 Correct 67 ms 10780 KB Output is correct
13 Correct 62 ms 10832 KB Output is correct
14 Correct 8 ms 2908 KB Output is correct
15 Correct 9 ms 2908 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 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 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 2792 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 7 ms 3176 KB Output is correct
12 Correct 58 ms 10772 KB Output is correct
13 Correct 62 ms 10836 KB Output is correct
14 Correct 7 ms 2908 KB Output is correct
15 Correct 5 ms 2936 KB Output is correct
16 Correct 1 ms 2648 KB Output is correct
17 Correct 18 ms 3676 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Incorrect 267 ms 84524 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 2692 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 8 ms 3272 KB Output is correct
12 Correct 61 ms 10728 KB Output is correct
13 Correct 66 ms 10932 KB Output is correct
14 Correct 8 ms 2904 KB Output is correct
15 Correct 5 ms 3140 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 18 ms 3808 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Incorrect 294 ms 84428 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory 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 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 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 2652 KB Output is correct
11 Correct 8 ms 3160 KB Output is correct
12 Correct 65 ms 10756 KB Output is correct
13 Correct 70 ms 10832 KB Output is correct
14 Correct 8 ms 2908 KB Output is correct
15 Correct 6 ms 3148 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 17 ms 3676 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Incorrect 268 ms 84564 KB Output isn't correct
21 Halted 0 ms 0 KB -