Submission #733592

#	Time	Username	Problem	Language	Result	Execution time	Memory
733592		SanguineChameleon	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	159 ms	262144 KiB

skyscraper

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 3e4 + 20;
const int maxC = 1e7 + 20;
const int inf = 1e9 + 20;
int B[maxN];
int P[maxN];
vector<pair<int, int>> adj[maxC];
int dist[maxC];

void just_do_it() {
	int N, M;
	cin >> N >> M;
	const int lim = 0;
	int cnt = N;
	for (int i = 0; i < M; i++) {
		cin >> B[i] >> P[i];
		if (P[i] > lim) {
			int cur = B[i] % P[i];
			int nxt = cur + P[i];
			for (; cur < N; cur += P[i], nxt += P[i]) {
				if (nxt < N) {
					adj[cnt].emplace_back(cnt + 1, 1);
					adj[cnt + 1].emplace_back(cnt, 1);
				}
				if (cur == B[i]) {
					adj[B[i]].emplace_back(cnt, 0);
				}
				adj[cnt].emplace_back(cur, 0);
				cnt++;
			}
		}
	}
	assert(cnt < maxC);
	for (int i = 0; i < cnt; i++) {
		dist[i] = inf;
	}
	dist[B[0]] = 0;
	deque<int> q = {B[0]};
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (auto p: adj[u]) {
			int v = p.first;
			int w = p.second;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				if (w == 0) {
					q.push_front(v);
				}
				else {
					q.push_back(v);
				}
			}
		}
	}
	if (dist[B[1]] == inf) {
		cout << -1;
	}
	else {
		cout << dist[B[1]];
	}
}

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