Submission #698335

#	Time	Username	Problem	Language	Result	Execution time	Memory
698335		jk410	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	119 ms	76612 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
#define compress(v) v.erase(unique(all(v)),v.end())
using namespace std;
const int INF = (int)1e9;
struct edge {
	int v, cost;
	bool operator<(const edge& tmp)const {
		return cost > tmp.cost;
	}
};
int N,M,SQRT;
int B[30000];
vector<int> P[30000];
bool Used[30000][173];
vector<edge> Edge[30000];
int Dist[30000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	SQRT = (int)sqrt(N);
	for (int i = 0; i < M; i++) {
		int p;
		cin >> B[i] >> p;
		if (p < SQRT)
			P[B[i]].push_back(p);
		else {
			for (int j = 1; B[i] - j * p >= 0; j++)
				Edge[B[i]].push_back({ B[i] - j * p,j });
			for (int j = 1; B[i] + j * p < N; j++)
				Edge[B[i]].push_back({ B[i] + j * p,j });
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j : P[i]) {
			for (int k = 1; i - k * j >= 0; k++) {
				Edge[i].push_back({ i - k * j,k });
				if (Used[i - k * j][j])
					break;
				Used[i - k * j][j] = true;
			}
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		fill(Used[i], Used[i] + SQRT, false);
		for (int j : P[i]) {
			for (int k = 1; i + k * j < N; k++) {
				Edge[i].push_back({ i + k * j,k });
				if (Used[i + k * j][j])
					break;
				Used[i + k * j][j] = true;
			}
		}
	}
	priority_queue<edge> q;
	fill(Dist, Dist + N, INF);
	Dist[B[0]] = 0;
	q.push({ B[0],0});
	while (!q.empty()) {
		auto t = q.top();
		q.pop();
		if (Dist[t.v] < t.cost)
			continue;
		for (edge i : Edge[t.v]) {
			if (Dist[i.v] > t.cost + i.cost) {
				Dist[i.v] = t.cost + i.cost;
				q.push({ i.v,Dist[i.v] });
			}
		}
	}
	int ans = Dist[B[1]];
	if (ans == INF)
		ans = -1;
	cout << ans;
	return 0;
}

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