Submission #564928

#	Time	Username	Problem	Language	Result	Execution time	Memory
564928		flappybird	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	631 ms	262144 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 40100
#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<int> locset;
vector<int> locs[MAX];
int N, M;
int findpv(int x) {
	int ind = upper_bound(locset.begin(), locset.end(), x) - locset.begin();
	ind--;
	if (ind < 0) return -1;
	else return locset[ind];
}
int findnx(int x) {
	int ind = lower_bound(locset.begin(), locset.end(), x) - locset.begin();
	if (ind >= M) return -1;
	else return locset[ind];
}
int np(int x, int p) { return x / p * p + p; }
int dist[MAX];
int vis[MAX];
vector<int> locp[MAX];
bool chk(vector<int>& v, int p) {
	int ind = lower_bound(v.begin(), v.end(), p) - v.begin();
	if (ind >= v.size() || v[ind] != p) return false;
	return true;
}
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]), locs[B[i]].push_back(i), locp[B[i]].push_back(P[i]);
	for (i = 0; i < N; i++) sort(locp[i].begin(), locp[i].end());
	sort(locset.begin(), locset.end());
	//locset.erase(unique(locset.begin(), locset.end()), locset.end());
	int j;
	for (i = 0; i < N; i++) {
		for (j = 1; j < locs[i].size(); j++) {
			adj[locs[i][j]].emplace_back(locs[i][j - 1], 0);
			adj[locs[i][j - 1]].emplace_back(locs[i][j], 0);
		}
	}
	for (i = 0; i < M; i++) {
		int delta = 1;
		while (1) {
			int loc = findpv(B[i] - delta);
			if (loc == -1) break;
			bool found = false;
			if ((B[i] - loc) % P[i] == 0) {
				if (chk(locp[loc], P[i])) {
					adj[i].emplace_back(locs[loc][0], (B[i] - loc) / P[i]);
					found = true;
				}
				else { for (auto v : locs[loc]) adj[i].emplace_back(v, (B[i] - loc) / P[i]); }
			}
			if (found) break;
			delta = B[i] - loc;
			delta = np(delta, P[i]);
		}
		delta = 1;
		while (1) {
			int loc = findnx(B[i] + delta);
			if (loc == -1) break;
			bool found = false;
			if ((loc - B[i]) % P[i] == 0) {
				if (chk(locp[loc], P[i])) {
					adj[i].emplace_back(locs[loc][0], (loc - B[i]) / P[i]);
					found = true;
				}
				else { for (auto v : locs[loc]) adj[i].emplace_back(v, (loc - B[i]) / P[i]); }
			}
			if (found) break;
			delta = loc - B[i];
			delta = np(delta, P[i]);
		}
	}
	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;
}

Compilation message (stderr)

skyscraper.cpp: In function 'bool chk(std::vector<int>&, int)':
skyscraper.cpp:40:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  if (ind >= v.size() || v[ind] != p) return false;
      |      ~~~~^~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (j = 1; j < locs[i].size(); j++) {
      |               ~~^~~~~~~~~~~~~~~~

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