Submission #733616

#	Time	Username	Problem	Language	Result	Execution time	Memory
733616		SanguineChameleon	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	196 ms	55184 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 = 6e6 + 20;
const int inf = 1e9 + 20;
int B[maxN];
int P[maxN];
vector<int> adj0[maxN];
bool can_nxt[maxC];
bool can_prv[maxC];
int dist[maxC];
int pos[maxC];
bool flag[maxN];
int id[maxN];

void just_do_it() {
	fill_n(pos, maxC, -1);
	int N, M;
	cin >> N >> M;
	const int lim = sqrt(N);
	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) {
					can_nxt[cnt] = true;
					can_prv[cnt + 1] = true;
				}
				if (cur == B[i]) {
					adj0[B[i]].emplace_back(cnt);
				}
				pos[cnt] = cur;
				cnt++;
				if (cnt == maxC) {
					exit(0);
				}
			}
		}
	}
	for (int d = 1; d <= lim; d++) {
		for (int i = 0; i < N; i++) {
			flag[i] = false;
		}
		bool found = false;
		for (int i = 0; i < M; i++) {
			if (P[i] == d) {
				found = true;
				break;
			}
		}
		if (!found) {
			continue;
		}
		for (int i = 0; i < d; i++) {
			int cur = i;
			int nxt = cur + d;
			for (; cur < N; cur += d, nxt += d) {
				if (nxt < N) {
					can_nxt[cnt] = true;
					can_prv[cnt + 1] = true;
				}
				id[cur] = cnt;
				pos[cnt] = cur;
				cnt++;
				if (cnt == maxC) {
					exit(0);
				}
			}
		}
		for (int i = 0; i < M; i++) {
			if (P[i] == d && !flag[B[i]]) {
				flag[B[i]] = true;
				adj0[B[i]].emplace_back(id[B[i]]);
			}
		}
	}
	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();
		if (u == B[1]) {
			cout << dist[u];
			return;
		}
		q.pop_front();
		if (u < N) {
			for (auto v: adj0[u]) {
				if (dist[u] < dist[v]) {
					dist[v] = dist[u];
					q.push_front(v);
				}
			}
		}
		else {
			if (pos[u] != -1) {
				int v = pos[u];
				if (dist[u] < dist[v]) {
					dist[v] = dist[u];
					q.push_front(v);
				}
			}
			if (can_nxt[u]) {
				int v = u + 1;
				if (dist[u] + 1 < dist[v]) {
					dist[v] = dist[u] + 1;
					q.push_back(v);
				}
			}
			if (can_prv[u]) {
				int v = u - 1;
				if (dist[u] + 1 < dist[v]) {
					dist[v] = dist[u] + 1;
					q.push_back(v);
				}
			}
		}
	}
	cout << -1;
}

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