Submission #1271168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271168		cmiuc	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	468 ms	316612 KiB

skyscraper

#include <iostream>
#include <vector>
#include <set>

using namespace std;
const int N = 30005, K = 180;
vector<pair<int,int>> nei[N * K];
int Min[N * K], a[N], p[N];

void dijkstra(){
	for (int i=1;i<N * K;i++)
		Min[i] = 1e9;

	Min[a[1]] = 0;
	set<pair<int,int>> st = {{0, a[1]}};

	while (st.size() > 0){
		auto [mn, u] = *st.begin();
		st.erase(begin(st));

		for (auto [i, w] : nei[u]){
			if (Min[i] > Min[u] + w){
				st.erase({Min[i], i});
				Min[i] = Min[u] + w;
				st.insert({Min[i], i});
			}
		}
	}
}

int main(){
	int n, m;
	cin>>n>>m;


	for (int i=1;i<K;i++){
		for (int j=1;j + i <= n;j++){
			nei[i * N + j].push_back({i + i * N + j, 1});
			nei[i * N + j + i].push_back({i * N + j, 1});
		}

		for (int j=1;j<=n;j++)
			nei[i * N + j].push_back({j, 0});
	}

	for (int i=1;i<=m;i++){
		cin>>a[i]>>p[i];
		a[i]++;
		if (p[i] >= K){
			for (int j=a[i] - p[i] * (a[i] / p[i]);j <= n;j += p[i])
				if (j != a[i])
					nei[a[i]].push_back({j, abs(a[i] - j) / p[i]});
		}
		else
			nei[a[i]].push_back({p[i] * N + a[i], 0});
	}
	dijkstra();

	if (Min[a[2]] == 1e9)
		Min[a[2]] = -1;
	cout<<Min[a[2]]<<endl;
}

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