Submission #239246

#TimeUsernameProblemLanguageResultExecution timeMemory
239246ant101Jakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
396 ms262148 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <iomanip> #include <fstream> #include <cmath> #include <vector> #include <set> #include <unordered_set> #include <unordered_map> #include <map> #include <stack> #include <queue> #include <assert.h> #include <limits> #include <cstdio> using namespace std; //#define RDEBUG 1 #ifdef RDEBUG #define D(x) x #else #define D(x) #endif #define inf 0x7fffffff #define MOD 1000000007 typedef long long ll; ll add(ll a, ll b) { a += b; if(a >= MOD) { a -= MOD; } return a; } ll sub(ll a, ll b) { a -= b; if(a < 0) { a += MOD; } return a; } ll mul(ll a, ll b) { return (a * b)%MOD; } void add_self(ll& a, ll b) { a = add(a, b); } void sub_self(ll& a, ll b) { a = sub(a, b); } void mul_self(ll& a, ll b) { a = mul(a, b); } const ll MAXN = 30010; ll sp[MAXN][175]; ll N, M; pair<ll, ll> doge[MAXN]; vector<pair<pair<ll, ll>, ll>> adj[MAXN][175]; void dij(ll start) { for (ll i = 0; i<N; i++) { for (ll j = 0; j<=sqrt(N); j++) { sp[i][j] = 1e13; } } priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq; pq.push({0, {doge[start].first, 0}}); sp[doge[start].first][0] = 0; while (pq.size() != 0) { ll d = pq.top().first, u = pq.top().second.first, p = pq.top().second.second; pq.pop(); if (sp[u][p] != d) { continue; } if (p != 0) { if (u-p >= 0) { adj[u][p].push_back({{u-p, p}, 1}); } if (u+p < N) { adj[u][p].push_back({{u+p, p}, 1}); } adj[u][p].push_back({{u, 0}, 0}); } for (auto edge : adj[u][p]) { ll v = edge.first.first, np = edge.first.second, w = edge.second; if (d+w < sp[v][np]) { sp[v][np] = d+w; pq.push({d+w, {v, np}}); } } if (p != 0) { if (u-p >= 0) { adj[u][p].pop_back(); } if (u+p < N) { adj[u][p].pop_back(); } adj[u][p].push_back({{u, 0}, 0}); } } } int main() { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; for (ll i = 0; i<M; i++) { ll a, b; cin >> a >> b; doge[i] = {a, b}; if (b<=sqrt(N)) { adj[a][0].push_back({{a, b}, 0}); } else { for (ll j = 1; j<=N; j++) { ll hold = 0; if (a-b*j >= 0) { hold++; adj[a][0].push_back({{a-b*j, 0}, j}); } if (a+b*j < N) { hold++; adj[a][0].push_back({{a+b*j, 0}, j}); } if (!hold) { break; } } } } dij(0); cout << (sp[doge[1].first][0] == 1e13 ? -1 : sp[doge[1].first][0]) << "\n"; return 0; }
#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...