Submission #23047

#	Time	Username	Problem	Language	Result	Execution time	Memory
23047		Bruteforceman	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	536 ms	26680 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
vector <int> g[30010];
const int magic = 173;
int n;

int table[180][30010];

int p[30010];
int b[30010];

class vertex {
public:
	int position;
	int power;
	vertex (int position, int power) : position (position), power (power) {}
	vertex (int position) : position (position) {
		power = 0;
	}
	vertex () {} 
	int distance() {
		return table[power][position];
	}
	void updateDist(int dist) {
		table[power][position] = min(table[power][position], dist);
	}
	bool good(int dist) {
		if(0 > position or position >= n) return false;
		if(this -> distance() <= dist) return false;
		else {
			this -> updateDist(dist);
			return true;
		}
	}
	void out() {
		cerr << position;
		if(power != 0) cerr << " " << power;
		cerr << endl;
	}
};

class event {
public: 
	vertex v;
	int dist;
	event () {}
	event (vertex v, int dist) : v(v), dist(dist) {}
	bool operator < (event e) const {
		return dist > e.dist;
	}
};

void shortest_path() {
	const int inf = table[0][0];
	
	priority_queue <event> Q;
	
	table[0][b[0]] = 0;
	Q.push(event(vertex(b[0]), 0));

	while(not Q.empty()) {
		event e = Q.top();
		Q.pop();
		// e.v.out();

		int dist = e.dist;
		vertex v = e.v;
		int cost;
		vertex u;

		if(v.power == 0) {
			for(int i : g[v.position]) {
				if(i <= magic) {
					cost = 1;

					u = vertex (v.position + i, i);
					if(u.good(cost + dist)) Q.push(event(u, cost + dist));

					u = vertex (v.position - i, i);
					if(u.good(cost + dist)) Q.push(event(u, cost + dist));

				} else {

					cost = 0;
					for(int pos = v.position + i; pos < n; pos += i) {
						u = vertex (pos);
						cost += 1;
						if(u.good(dist + cost)) Q.push(event(u, dist + cost));
					}

					cost = 0;
					for(int pos = v.position - i; pos >= 0; pos -= i) {
						u = vertex (pos);
						cost += 1;
						if(u.good(dist + cost)) Q.push(event(u, dist + cost));
					}
				}
			}
		} else {
			cost = 1;
			u = vertex (v.position + v.power, v.power);
			if(u.good(cost + dist)) Q.push(event(u, cost + dist));

			u = vertex (v.position - v.power, v.power);
			if(u.good(cost + dist)) Q.push(event(u, cost + dist));

			u = vertex (v.position);
			if(u.good(dist)) Q.push(event(u, dist));
		}
	}
	int ans = table[0][b[1]];
	ans = (ans == inf) ? -1 : ans;
	printf("%d\n", ans);
}

int main(int argc, char const *argv[])
{
	memset(table, 63, sizeof table);
	int m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		scanf("%d %d", b + i, p + i);
		g[b[i]].push_back(p[i]);
	}
	shortest_path ();
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:120:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
skyscraper.cpp:122:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", b + i, p + i);
                               ^

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