Submission #472059

#	Time	Username	Problem	Language	Result	Execution time	Memory
472059		hhhhaura	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1096 ms	246340 KiB

skyscraper

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

const int maxn = 3e4, maxb = 175, maxv = 1.05e7, maxe = 2.1e7, magic = 1 << 20;

int n, m, cnt, bnd, s, t, l, r, Q[magic + 3], pnt[maxb + 3][maxn + 3], tot, msk[maxe + 3], nxt[maxe + 3], lnk[maxv + 3], dist[maxv + 3];

bool vis[maxb + 3][maxb + 3];

void add(int u, int v, int w) {

	msk[++tot] = v * 2 + w;

	nxt[tot] = lnk[u], lnk[u] = tot;

}

int main() {

	scanf("%d %d", &n, &m);

	cnt = n, bnd = sqrt(m) + .5;

	for (int i = 1, b, p; i <= m; i++) {

		scanf("%d %d", &b, &p);

		b++;

		if (i == 1) s = b;

		if (i == 2) t = b;

		if (p > bnd) {

			int x = ++cnt, u = x, v;

			add(b, x, 0);

			for (int i = b - p; i >= 1; i -= p) {

				v = ++cnt;

				add(u, v, 1);

				add(v, i, 0);

				u = v;

			}

			u = x;

			for (int i = b + p; i <= n; i += p) {

				v = ++cnt;

				add(u, v, 1);

				add(v, i, 0);

				u = v;

			}

		} else {

			if (!vis[p][b % p]) {

				vis[p][b % p] = 1;

				int x = (b - 1) % p + 1;

				for (int i = x; i <= n; i += p) {

					add(pnt[p][i] = ++cnt, i, 0);

					if (i > x) {

						add(pnt[p][i], pnt[p][i - p], 1);

						add(pnt[p][i - p], pnt[p][i], 1);

					}

				}

			}

			add(b, pnt[p][b], 0);

		}

	}

	memset(dist, -1, sizeof(dist));

	Q[r++] = s;

	dist[s] = 0;

	while (l != r) {

		int u = Q[l++];

		if (l == magic) l = 0;

		if (u == t) break;

		for (int i = lnk[u], v, w; i; i = nxt[i]) {

			v = msk[i] >> 1, w = msk[i] & 1;

			if (~dist[v]) continue;

			dist[v] = dist[u] + w;

			if (w) {

				Q[r++] = v;

				if (r == magic) r = 0;

			} else {

				if (--l < 0) l = magic - 1;

				Q[l] = v;

			}

		}

	}

	printf("%d\n", dist[t]);

	return 0;

}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d %d", &b, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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