Submission #244799

#	Time	Username	Problem	Language	Result	Execution time	Memory
244799		vioalbert	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	231 ms	67172 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e4+5, MAX = 2e9;
int n, m, batas;
vector<pair<int, int>> adj[N];
set<int> power[N];
int location[N], p[N];

typedef pair<int, int> state;

int dijkstra(int s, int e) {
	vector<bool> vis(n+1, 0);
	vector<int> dist(n+1, MAX);
	priority_queue<state, vector<state>, greater<state>> pq;
	pq.push({0, s});
	dist[s] = 0;

	while(!pq.empty()) {
		int u = pq.top().second; pq.pop();
		if(u == e) return dist[e];
		if(!vis[u]) {
			vis[u] = 1;
			for(auto& it : adj[u]) {
				int v = it.first, d = it.second;
				if(dist[v] > dist[u] + d) {
					dist[v] = dist[u] + d;
					pq.push({dist[v], v});
				}
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> location[i] >> p[i];
		power[location[i]].insert(p[i]);
	}

	for(int i = 0; i < n; i++) {
		for(auto x : power[i]) {
			int lst = -1;
			for(int j = i%x; j < n; j+=x) {
				if(power[j].count(x) > 0) {
					if(lst >= 0) {
						adj[lst].push_back({j, abs(lst-j)/x});
						adj[j].push_back({lst, abs(lst-j)/x});
					}
					for(int k = j-x; k > lst; k-=x)
						adj[j].push_back({k, abs(k-j)/x});
					lst = j;
					if(i != j) power[j].erase(x);
				} else if(lst >= 0) {
					adj[lst].push_back({j, abs(lst-j)/x});
				}
			}
		}
		power[i].clear();
	}

	int ans = dijkstra(location[0], location[1]);
	cout << ans << '\n';

	return 0;
}

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