Submission #389730

#	Time	Username	Problem	Language	Result	Execution time	Memory
389730		milleniumEeee	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	125 ms	262148 KiB

skyscraper

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;

const int MAXN = (int)2e5 + 5;
const int SHIFT = 50000;
const int S = 175;
const int INF = 1e18;

int pos[MAXN], p[MAXN];
int n, m;

struct node {
	int v, pw, cost;
	node () {
		
	}
	node (int v_, int pw_, int cost_) {
		v = v_;
		pw = pw_;
		cost = cost_;
	}
};

struct Compare_node {
	bool operator () (node const &p1, node const &p2) {
		return p1.cost < p2.cost;
	}
};

vector <int> big[MAXN];
set <int> small[MAXN];
vector <node> g[MAXN][S];
int dist[MAXN][S];

bool in(int pos) {
	return 0 <= pos && pos < n;
}

signed main() {
	fastInp;
	cin >> n >> m;
	set <int> all_small;
	for (int i = 0; i < m; i++) {
		cin >> pos[i] >> p[i];
		if (p[i] >= S) {
			big[pos[i]].pb(p[i]);
		} else {
			small[pos[i]].insert(p[i]);
			all_small.insert(p[i]);
		}
	}
	// node -> v pw cost
	for (int i = 0; i < n; i++) {
		for (int val : all_small) {
			if (in(i - val)) {
				g[i][val].pb(node(i - val, val, 1));
			}
			if (in(i + val)) {
				g[i][val].pb(node(i + val, val, 1));
			}
		}
		for (int val : small[i]) {
			g[i][0].pb(node(i, val, 0));
		}
	}
	priority_queue <node, vector<node>, Compare_node> pq;
	vector <bool> used(MAXN, false);
	memset(dist, -1, sizeof(dist));
	pq.push(node(pos[0], 0, 0));
	dist[pos[0]][0] = 0;
	while (!pq.empty()) {
		int v = pq.top().v;
		int pw = pq.top().pw;
		int cost = -pq.top().cost;
		pq.pop();
		if (cost > dist[v][pw]) {
			continue;
		}
		if (!used[v]) { // впервые добрались до v
			used[v] = 1;
			for (int el : big[v]) {
				for (int to = v % el; to < n; to += el) {
					int c = abs(v - to) / el;
					if (dist[to][0] == -1 || dist[to][0] > cost + c) {
						dist[to][0] = cost + c;
						pq.push(node(to, 0, -dist[to][0]));
					}
				}
			}
		}
		// change our pw
		if (dist[v][0] == -1 || dist[v][0] > dist[v][pw]) {
			dist[v][0] = dist[v][pw];
			pq.push(node(v, 0, -dist[v][pw]));
		}
		for (auto el : g[v][pw]) {
			int new_v = el.v;
			int new_pw = el.pw;			
			int c = el.cost;
			if (dist[new_v][new_pw] == -1 || dist[new_v][new_pw] > dist[v][pw] + c) {
				dist[new_v][new_pw] = dist[v][pw] + c;
				pq.push(node(new_v, new_pw, -dist[new_v][new_pw]));
			}
		}
	}
	cout << dist[pos[1]][0] << endl;
}

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