Submission #564624

#TimeUsernameProblemLanguageResultExecution timeMemory
564624flappybirdJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms468 KiB
#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, -1)) - 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, INF)) - 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; } 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 = 0; 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 = 0; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...