Submission #826698

#	Time	Username	Problem	Language	Result	Execution time	Memory
826698		happypotato	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	559 ms	225668 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int MAX = 1e9;
const int mxN = 3e4;
const int SQRT = 80;
pii doge[mxN];
vector<pii> adj[mxN * (SQRT + 1)];
int dist[mxN * (SQRT + 1)];
void AddEdge(int u, int v, int w) {
	adj[u].pb({v, w});
}
int n;
void init() {
	for (int i = 0; i < mxN * (SQRT + 1); i++) {
		adj[i].clear();
		dist[i] = MAX;
	}
	// dummy nodes for P_i < SQRT
	for (int diff = 1; diff <= min(n, SQRT); diff++) {
		for (int i = 0; i < n; i++) {
			AddEdge(diff * mxN + i, i, 0);
		}
		for (int i = diff; i < n; i++) {
			int u = diff * mxN + (i - diff);
			int v = diff * mxN + i;
			AddEdge(u, v, 1);
			AddEdge(v, u, 1);
		}
	}
}
void solve() {
	int m;
	cin >> n >> m;
	init();
	for (int i = 0; i < m; i++) {
		cin >> doge[i].ff >> doge[i].ss;
		if (doge[i].ss <= SQRT) {
			// connect to dummy nodes
			AddEdge(doge[i].ff, doge[i].ss * mxN + doge[i].ff, 0);
		} else {
			// connect actual edges
			for (int step = 1; doge[i].ff + doge[i].ss * step < n; step++) {
				AddEdge(doge[i].ff, doge[i].ff + doge[i].ss * step, step);
			}
			for (int step = 1; doge[i].ff - doge[i].ss * step >= 0; step++) {
				AddEdge(doge[i].ff, doge[i].ff - doge[i].ss * step, step);
			}
		}
	}
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, doge[0].ff});
	dist[doge[0].ff] = 0;
	while (!pq.empty()) {
		pii cur = pq.top();
		pq.pop();
		if (dist[cur.ss] > cur.ff) continue;
		for (pii &v : adj[cur.ss]) {
			if (cur.ff + v.ss >= dist[v.ff]) continue;
			dist[v.ff] = cur.ff + v.ss;
			pq.push({dist[v.ff], v.ff});
		}
	}
	int ans = dist[doge[1].ff];
	cout << (ans >= MAX ? -1 : ans) << endl;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

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