Submission #826695

#	Time	Username	Problem	Language	Result	Execution time	Memory
826695		happypotato	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	57 ms	86732 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 = 100;
pii doge[mxN];
vector<pii> adj[mxN * (SQRT + 1)];
int dist[mxN * (SQRT + 1)];
void AddEdge(int u, int v, bool 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
			int cur;
			cur = doge[i].ff;
			while (cur + doge[i].ss < n) {
				AddEdge(cur, cur + doge[i].ss, 1);
				cur += doge[i].ss;
			}
			cur = doge[i].ff;
			while (cur - doge[i].ss >= 0) {
				AddEdge(cur, cur - doge[i].ss, 1);
				cur -= doge[i].ss;
			}
		}
	}
	// 0-1 BFS
	deque<pii> dq;
	dq.push_back({doge[0].ff, 0});
	dist[doge[0].ff] = 0;
	while (!dq.empty()) {
		pii cur = dq.front();
		dq.pop_front();
		if (dist[cur.ff] > cur.ss) continue;
		for (pii &v : adj[cur.ff]) {
			if (cur.ss + v.ss >= dist[v.ff]) continue;
			dist[v.ff] = cur.ss + v.ss;
			if (!v.ss) dq.push_front({v.ff, dist[v.ff]});
			else dq.push_back({v.ff, dist[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: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43