oj.uz

Submission #958538

# Submission time Handle Problem Language Result Execution time Memory
958538 2024-04-06T01:55:55 Z MinaRagy06 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 2 ms 3688 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 30'005, B = 3;
vector<int> gud[N];
int dist[N][B + 5][2], ok[N][B + 5];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m;
	int st = -1, en = -1;
	for (int i = 0; i < m; i++) {
		int b, p;
		cin >> b >> p;
		if (i == 0) st = b;
		if (i == 1) en = b;
		if (p < B) {
			ok[b][p] = 1;
		}
		gud[b].push_back(p);
	}
	memset(dist, '?', sizeof dist);
	priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> pq;
	pq.push({0, st, B, 0});
	dist[st][B][0] = 0;
	while (pq.size()) {
		int cost = pq.top()[0];
		int node = pq.top()[1];
		int pp = pq.top()[2];
		int ok2 = pq.top()[3];
		pq.pop();
		if (cost > dist[node][pp][ok2]) continue;
		if (pp < B) {
			int p = pp;
			if (p - 1 >= 0 && cost < dist[node][p - 1][0]) {
				dist[node][p - 1][0] = cost;
				pq.push({cost, node, p - 1, 0});
			}
			if (cost < dist[node][p + 1][0]) {
				dist[node][p + 1][0] = cost;
				pq.push({cost, node, p + 1, 0});
			}
			if (!ok[node][p] && !ok2) continue;
			if (node - p >= 0 && cost + 1 < dist[node - p][p][1]) {
				dist[node - p][p][1] = cost + 1;
				pq.push({cost + 1, node - p, p, 1});
			}
			if (node + p < n && cost + 1 < dist[node + p][p][1]) {
				dist[node + p][p][1] = cost + 1;
				pq.push({cost + 1, node + p, p, 1});
			}
		} else {
			if (cost < dist[node][pp - 1][0]) {
				dist[node][pp - 1][0] = cost;
				pq.push({cost, node, pp - 1, 0});
			}
			for (auto p : gud[node]) {
				if (p < B) continue;
				int cnt = 0;
				for (int nxt = node + p; nxt < n; nxt += p) {
					cnt++;
					if (cost + cnt < dist[nxt][B][0]) {
						dist[nxt][B][0] = cost + cnt;
						pq.push({cost + cnt, nxt, B, 0});
					}
				}
				cnt = 0;
				for (int nxt = node - p; nxt >= 0; nxt -= p) {
					cnt++;
					if (cost + cnt < dist[nxt][B][0]) {
						dist[nxt][B][0] = cost + cnt;
						pq.push({cost + cnt, nxt, B, 0});
					}
				}
			}
		}
	}
	cout << dist[en][B][0] << '\n';
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3688 KB Output is correct
4 Incorrect 1 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Incorrect 1 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Incorrect 1 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Incorrect 1 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Incorrect 1 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -