Submission #453279

#	Time	Username	Problem	Language	Result	Execution time	Memory
453279		nonsensenonsense1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	465 ms	262148 KiB

skyscraper

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

struct node {
	int pos, dist;
	node *left, *right;
	bool vis;
	node(int pos_ = -1) {
		pos = pos_;
		left = right = 0;
		vis = false;
		dist = ~(1 << 31);
	}
};

const int N = 30000;
const int K = 180;
int n, m;
node g[K][N];
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].pos = j;
			if (i) {
				if (j >= i) g[i][j].left = g[i] + j - i;
				if (j + i < N) g[i][j].right = g[i] + j + i;
			}
		}
	}
	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 {
			node *r = new node(b);
			top[b].push_back(r);
			node *prev = r;
			for (int j = b - p; j >= 0; j -= p) {
				node *cur = new node(j);
				cur->right = prev;
				prev->left = cur;
				prev = cur;
			}
			prev = r;
			for (int j = b + p; j < N; j += p) {
				node *cur = new node(j);
				cur->left = prev;
				prev->right = cur;
				prev = cur;
			}
		}
	}
	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->left) go(cur, cur->left, 1);
				if (cur->right) go(cur, cur->right, 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:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", &b, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:89:14: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |  if (g[0][t].dist == ~(1 << 31)) printf("-1\n");
      |      ~~~~~~~~^~~~
skyscraper.cpp:75:22: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |  dq.push_back(g[0] + s);
      |                      ^

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