Submission #879516

#	Time	Username	Problem	Language	Result	Execution time	Memory
879516		serifefedartar	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	1880 KiB

skyscraper

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 3e4 + 100;

int B[MAXN], P[MAXN];
bool vis[MAXN];
vector<vector<pair<int,int>>> graph;
vector<int> dist;
set<int> places[MAXN];

int main() {
	int N, M;
	cin >> N >> M;

	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	dist = vector<int>(N+1, 1e8);
	for (int i = 1; i <= M; i++) {
		cin >> B[i] >> P[i];
		B[i]++;
		places[P[i]].insert(B[i]);
	}

	for (int i = 1; i < MAXN; i++) {
		if (places[i].size() == 0)
			continue;

		for (auto u : places[i]) {
			for (int p = u - i; p >= 1; p -= i) {
				graph[u].push_back({p, (u - p) / i});
				if (places[i].count(p))
					break;
			}
			for (int p = u + i; p <= N; p += i) {
				graph[u].push_back({p, (p - u) / i});
				if (places[i].count(p))
					break;
			}
		}
	}

	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0, 1});
	dist[1] = 0;

	while (!pq.empty()) {
		int node = pq.top().s;
		int d = pq.top().f;
		pq.pop();

		if (vis[node])
			continue;
		vis[node] = true;

		for (auto u : graph[node]) {
			if (dist[u.f] > dist[node] + u.s) {
				dist[u.f] = dist[node] + u.s;
				pq.push({dist[u.f], u.f});
			}
		}
	}

	cout << (dist[B[2]] >= 1e7 ? -1 : dist[B[2]]) << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:54:7: warning: unused variable 'd' [-Wunused-variable]
   54 |   int d = pq.top().f;
      |       ^

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