제출 #564711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564711		flappybird	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	572 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define MAX 10100
#define MAXS 20
#define INF 1010101010
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> adj[MAX];
int B[MAX];
int P[MAX];
vector<pii> locset;
int N, M;
int findpv(int x) {
	int ind = upper_bound(locset.begin(), locset.end(), pii(x, INF)) - locset.begin();
	ind--;
	if (ind < 0) return -1;
	else return locset[ind].second;
}
int findnx(int x) {
	int ind = upper_bound(locset.begin(), locset.end(), pii(x, -1)) - locset.begin();
	if (ind >= M) return -1;
	else return locset[ind].second;
}
int np(int x, int p) {
	if (x % p) return x / p * p + p;
	else return x + p;
}
int dist[MAX];
int vis[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i;
	for (i = 0; i < M; i++) cin >> B[i] >> P[i], locset.emplace_back(B[i], i);
	sort(locset.begin(), locset.end());
	for (i = 0; i < M; i++) {
		int delta = 1;
		while (1) {
			int v = findpv(B[i] - delta);
			if (v == -1) break;
			if ((B[i] - B[v]) % P[i] == 0) {
				adj[i].emplace_back(v, (B[i] - B[v]) / P[i]);
				if (P[v] == P[i]) break;
			}
			delta = B[i] - B[v];
			delta = np(delta, P[i]);
			if (B[i] < delta) break;
		}
		delta = 1;
		while (1) {
			int v = findnx(B[i] + delta);
			if (v == -1) break;
			if ((B[v] - B[i]) % P[i] == 0) {
				adj[i].emplace_back(v, (B[v] - B[i]) / P[i]);
				if (P[v] == P[i]) break;
			}
			delta = B[v] - B[i];
			delta = np(delta, P[i]);
			if (B[i] + delta >= N) break;
		}
	}
	for (i = 1; i < M; i++) dist[i] = INF;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.emplace(0, 0);
	while (pq.size()) {
		int v = pq.top().second;
		pq.pop();
		if (vis[v]) continue;
		vis[v] = 1;
		for (auto &[x, c] : adj[v]) {
			if (vis[x]) continue;
			if (dist[x] > dist[v] + c) {
				dist[x] = dist[v] + c;
				pq.emplace(dist[x], x);
			}
		}
	}
	if (dist[1] >= INF) dist[1] = -1;
	cout << dist[1] << Ln;
}

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