Submission #102822

#	Time	Username	Problem	Language	Result	Execution time	Memory
102822		Noam527	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	356 ms	121496 KiB

skyscraper

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

const int lim = 1000003;

struct edge {
	int to, w;
	edge(int tt, int ww) {
		to = tt;
		w = ww;
	}
	bool operator < (const edge &a) const {
		return w > a.w;
	}
};

int n, m;
int B[30003], P[30003];
vector<edge> g[30003];
map<pair<int, int>, vector<int>> M;

int d[30003];
vector<int> nxt[lim];

void add(vector<int> &pos, int len) {
	sort(pos.begin(), pos.end());
	int l, r;
	for (int i = 0; i < pos.size(); i++) {
		l = (i == 0 ? 0 : pos[i - 1]);
		r = (i == (int)pos.size() - 1 ? n - 1 : pos[i + 1]);
		for (int j = pos[i] - len; j >= l; j -= len)
			g[pos[i]].push_back(edge(j, (pos[i] - j) / len));
		for (int j = pos[i] + len; j <= r; j += len)
			g[pos[i]].push_back(edge(j, (j - pos[i]) / len));
	}
}

void dijkstra() {
	for (int i = 0; i < n; i++) d[i] = -1;
	
	nxt[0].push_back(B[0]);
	for (int dis = 0; d[B[1]] == -1 && dis <= lim; dis++) {
		for (const auto &x : nxt[dis]) {
			if (d[x] != -1) continue;
			d[x] = dis;
			for (const auto &i : g[x])
				if (dis + i.w <= lim && d[i.to] == -1)
					nxt[dis + i.w].push_back(i.to);
		}
	}
	
	/*
	priority_queue<edge> q;
	q.push(edge(B[0], 0));
	while (q.size()) {
		edge x = q.top();
		q.pop();
		if (d[x.to] != -1) continue;
		d[x.to] = x.w;
		for (const auto &i : g[x.to])
			if (d[i.to] == -1)
				q.push(edge(i.to, x.w + i.w));
	}
	*/
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> B[i] >> P[i];
		M[{B[i] % P[i], P[i]}].push_back(B[i]);
	}
	for (auto &i : M) add(i.second, i.first.second);
	dijkstra();
	cout << d[B[1]] << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'void add(std::vector<int>&, int)':
skyscraper.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pos.size(); i++) {
                  ~~^~~~~~~~~~~~

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