Submission #279585

#	Time	Username	Problem	Language	Result	Execution time	Memory
279585		srvlt	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	182 ms	40960 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 2003, m0 = 30003;
int n, m, can[n0][n0], ans[n0], inf;
vector <int> d[n0];
vector <array <int, 2>> g[n0];

void dijsktra(int x) {
	priority_queue <array <int, 2>, vector <array <int, 2>>, greater <array <int, 2>>> q;
	memset(& ans, 0x3f, sizeof(ans));
	inf = ans[0];
	ans[x] = 0;
	q.push({ans[x], x});
	while (!q.empty()) {
		auto V = q.top();
		q.pop();
		int v = V[1];
		if (ans[v] < V[0]) continue;
		for (auto & i : g[v]) {
			int to = i[0], w = i[1];
			if (ans[to] > ans[v] + w) {
				ans[to] = ans[v] + w;
				q.push({ans[to], to});
			}
		}
	}
	
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m;
	int A = -1, B = -1;
	for (int i = 0; i < m; i++) {
		int x, p;
		cin >> x >> p;
		if (i == 0) A = x;
		if (i == 1) B = x;
		can[x][p] = 1;
	}
	for (int i = 1; i <= n; i++)
		for (int j = i; j >= 1; j--)
			if (i % j == 0) d[i].pb(j);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			int dist = abs(i - j), res = -1;
			for (int k : d[dist]) {
				if (can[i][k]) {
					res = dist / k;
					break;
				}
			}
			if (res == -1) continue;
			g[i].pb({j, res});
		}
	}
	dijsktra(A);
	if (ans[B] == inf) ans[B] = -1;
	cout << ans[B];
}

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