Submission #879501

#	Time	Username	Problem	Language	Result	Execution time	Memory
879501		serifefedartar	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1116 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,ll>>> graph;
vector<int> dist;
vector<int> places[MAXN];

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

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

	for (int i = 1; i < MAXN; i++) {
		if (places[i].size() == 0)
			continue;
		places[i].push_back(1);
		sort(places[i].begin(), places[i].end());
		places[i].push_back(N);

		for (int j = 1; j < places[i].size() - 1; j++) {
			int plc = places[i][j];
			for (int p = plc - i; p >= places[i][j-1]; p -= i)
				graph[plc].push_back({p, (plc - p) / i});
			for (int p = plc + i; p <= places[i][j+1]; p += i)
				graph[plc].push_back({p, (p - plc) / i});
		}
	}

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

	while (!pq.empty()) {
		int node = pq.top().s;
		ll 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[2] >= 1e7 ? -1 : dist[2]) << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int j = 1; j < places[i].size() - 1; j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:52:6: warning: unused variable 'd' [-Wunused-variable]
   52 |   ll d = pq.top().f;
      |      ^

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