Submission #453329

#	Time	Username	Problem	Language	Result	Execution time	Memory
453329		nonsensenonsense1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	241 ms	170192 KiB

skyscraper

#include <cstdio>
#include <vector>
#include <deque>

struct node {
	int dist, step, pos;
	bool vis;
	node() {
		vis = false;
		dist = ~(1 << 31);
	}
};

const int N = 30000;
const int K = 180;
int n, m;
node g[K][N], d[N][K];
std::vector<node *> top[N];
std::deque<node *> dq;

void go(node *cur, node *to, bool w) 
{
	if (to->dist > cur->dist + w) {
		to->dist = cur->dist;
		if (w) {
			++to->dist;
			dq.push_back(to);
		}
		else dq.push_front(to);
	}
}

int main() 
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < K; ++i) for (int j = 0; j < N; ++j) {
		g[i][j].step = i;
		g[i][j].pos = j;
	}
	int s, t;
	for (int i = 0; i < m; ++i) {
		int b, p;
		scanf("%d%d", &b, &p);
		if (!i) s = b;
		if (i == 1) t = b;
		if (p < K) top[b].push_back(g[p] + b);
		else for (int j = b % p; j < n; j += p) {
			if (j == b) top[b].push_back(d[i] + j / p);
			d[i][j / p].step = p;
			d[i][j / p].pos = j;
		}
	}
	g[0][s].dist = 0;
	dq.push_back(g[0] + s);
	while (!dq.empty()) {
		node *cur = dq.front();
		dq.pop_front();
		if (!cur->vis) {
			cur->vis = true;
			if (cur >= g[0] && cur < g[1]) for (int i = 0; i < (int)top[cur->pos].size(); ++i) go(cur, top[cur->pos][i], 0);
			else {
				go(cur, g[0] + cur->pos, 0);
				if (cur->pos - cur->step >= 0) go(cur, cur >= g[0] && cur <= g[K - 1] ? cur - cur->step : cur - 1, 1);
				if (cur->pos + cur->step < N) go(cur, cur >= g[0] && cur <= g[K - 1] ? cur + cur->step : cur + 1, 1);
			}
		}
	}
	if (g[0][t].dist == ~(1 << 31)) printf("-1\n");
	else printf("%d\n", g[0][t].dist);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &b, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:68:14: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  if (g[0][t].dist == ~(1 << 31)) printf("-1\n");
      |      ~~~~~~~~^~~~
skyscraper.cpp:54:22: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  dq.push_back(g[0] + s);
      |                      ^

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