Submission #879551

#TimeUsernameProblemLanguageResultExecution timeMemory
879551Shayan86Jakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
501 ms4056 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define Mp make_pair #define sep ' ' #define endl '\n' #define F first #define S second #define pb push_back #define all(x) (x).begin(),(x).end() #define kill(res) cout << res << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 3e4 + 50; const ll inf = 15e8; int n, m, b[N], dist[N]; bool mark[N]; vector<int> pw[N]; void dijk(int v){ fill(dist, dist + N, inf); priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push(Mp(0, v)); dist[v] = 0; while(!pq.empty()){ int v = pq.top().S; pq.pop(); if(mark[v]) continue; mark[v] = true; for(int p: pw[v]){ for(int u = v+p, i = 1; u < n; u += p, i++){ if(dist[u] > dist[v] + i){ dist[u] = dist[v] + i; pq.push(Mp(dist[u], u)); } } for(int u = v-p, i = 1; u >= 0; u -= p, i++){ if(dist[u] > dist[v] + i){ dist[u] = dist[v] + i; pq.push(Mp(dist[u], u)); } } } } } int main(){ fast_io; cin >> n >> m; int p; for(int i = 0; i < m; i++){ cin >> b[i] >> p; pw[b[i]].pb(p); } dijk(b[0]); if(dist[b[1]] >= inf) kill(-1); kill(dist[b[1]]); }
#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...