Submission #954926

#	Time	Username	Problem	Language	Result	Execution time	Memory
954926		colossal_pepe	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	906 ms	3532 KiB

skyscraper

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

const int INF = 1e9;
const int BLK = 200;

int n, m;
vector<int> b, p;
vector<vector<int>> v;

void addDoge(int i, int pos, int d, vector<int> &dist, priority_queue<pair<int, int>> &q, bool dir) {
	int c = (dir ? 1 : -1);
	for (int pos_nxt = pos + c * p[i], x = 1; (dir ? pos_nxt < n : pos_nxt >= 0); pos_nxt += c * p[i], x++) {
		if (-d + x < dist[pos_nxt]) {
			dist[pos_nxt] = -d + x;
			q.push({d - x, pos_nxt});
		}
	}
}
 
int solve() {
	vector<int> dist(n, INF);
	priority_queue<pair<int, int>> q;
	dist[b[0]] = 0;
	q.push({0, b[0]});
	while (not q.empty()) {
		auto [d, pos] = q.top();
		q.pop();
		if (dist[pos] != -d) continue;
		while (not v[pos].empty()) {
			addDoge(v[pos].back(), pos, d, dist, q, 0);
			addDoge(v[pos].back(), pos, d, dist, q, 1);
			v[pos].pop_back();
		}
		// if (power and pos + power < n and -d + 1 < dist[pos + power][power]) {
		// 	dist[pos + power][power] = -d + 1;
		// 	q.push(make_tuple(d - 1, pos + power, power));
		// }
		// if (power and pos - power >= 0 and -d + 1 < dist[pos - power][power]) {
		// 	dist[pos - power][power] = -d + 1;
		// 	q.push(make_tuple(d - 1, pos - power, power));
		// }
	}
	int ret = INF;
	for (int i = 0; i < BLK; i++) {
		ret = min(ret, dist[b[1]]);
	}
	return ret == INF ? -1 : ret;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	v.resize(n), b.resize(m), p.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i] >> p[i];
		v[b[i]].push_back(i);
	}
	cout << solve() << '\n';
	return 0;
}

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