Submission #991031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991031	2024-06-01T05:39:03 Z	stdfloat	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	360 KB

skyscraper

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

#define int long long

#define ff  first
#define ss  second
#define pii pair<int, int>

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	int n, m;
	cin >> n >> m;
 
	vector<int> X(m), P(n);
	for (int i = 0; i < m; i++)
		cin >> X[i] >> P[X[i]];
 
	vector<int> dis(n, INT_MAX); dis[X[0]] = 0;
	priority_queue<pair<int, pii>> q; q.push({0, {X[0], P[X[0]]}});
	while (!q.empty()) {
		int d = q.top().ff;
		auto [x, p] = q.top().ss; q.pop();

		if (x == X[1]) return cout << dis[x], 0;
 
		if (-d != dis[x]) continue;
 
		for (int i = x; i >= 0; i -= p) {
			if (dis[x] + (x - i) / p < dis[i]) {
				dis[i] = dis[x] + (x - i) / p;
				q.push({-dis[i], {i, (P[i] ? P[i] : p)}});
			}
		}
		for (int i = x; i < n; i += p) {
			if (dis[x] + (i - x) / p < dis[i]) {
				dis[i] = dis[x] + (i - x) / p;
				q.push({-dis[i], {i, (P[i] ? P[i] : p)}});
			}
		}
	}
 
	cout << -1;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	360 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Halted	0 ms	0 KB	-