Submission #626912

#	Time	Username	Problem	Language	Result	Execution time	Memory
626912		as111	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	388 ms	73824 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MAXN 7600000
using namespace std;
int n, m, Num[MAXN], D[MAXN], Q1[MAXN], Q2[MAXN];
vector<int>E[30100];
map<int, int>Map;
bool be[MAXN], ed[MAXN];
struct A {
	int a, b;
}w[30100];
int cnt;
void Make(int a, int b, int x) {
	int i;
	be[cnt + 1] = true;
	for (i = b; i < n; i += a) {
		++cnt;
		Num[cnt] = i;
		if (x == i) E[x].push_back(cnt);
	}
	ed[cnt] = true;
}
void BFS(int a) {
	int i, h = 0, t = 0, tt = 0, x;
	for (i = 0; i <= cnt; i++)D[i] = 999999999;
	D[a] = 0;
	Q1[++t] = a;
	while (t) {
		while (h < t) {
			x = Q1[++h];
			if (x < n) {
				for (i = 0; i < E[x].size(); i++) {
					if (D[E[x][i]] > D[x]) {
						D[E[x][i]] = D[x];
						Q1[++t] = E[x][i];
					}
				}
			}
			else {
				if (D[Num[x]] > D[x]) {
					D[Num[x]] = D[x];
					Q1[++t] = Num[x];
				}
			}
		}
		tt = 0;
		for (i = 1; i <= t; i++) {
			if (Q1[i] < n)continue;
			x = Q1[i];
			if (!be[x] && D[x - 1] > D[x] + 1) {
				D[x - 1] = D[x] + 1;
				Q2[++tt] = x - 1;
			}
			if (!ed[x] && D[x + 1] > D[x] + 1) {
				D[x + 1] = D[x] + 1;
				Q2[++tt] = x + 1;
			}
		}
		for (i = 1; i <= tt; i++)Q1[i] = Q2[i];
		t = tt;
		h = 0;
	}
}
int main() {
	int i, p1, p2, t;
	scanf("%d%d", &n, &m);
	cnt = n;
	for (i = 1; i <= m; i++) {
		scanf("%d%d", &w[i].a, &w[i].b);
		t = w[i].b * 30100 + (w[i].a % w[i].b);
		if (!Map[t]) {
			Map[t] = cnt + 1;
			Make(w[i].b, w[i].a % w[i].b, w[i].a);
		}
		else {
			E[w[i].a].push_back(Map[t] + w[i].a / w[i].b);
		}
	}
	p1 = w[1].a, p2 = w[2].a;
	BFS(p1);
	printf("%d\n", D[p2] == 999999999 ? -1 : D[p2]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'void BFS(int)':
skyscraper.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (i = 0; i < E[x].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d%d", &w[i].a, &w[i].b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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