Submission #1248381

#TimeUsernameProblemLanguageResultExecution timeMemory
1248381shiocanJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> #include <cstdlib> #include <stdlib.h> using namespace std; #define ull unsigned long long #define ld long double #define ll long long #define int long long #define pii pair<int, int> #define all(v) v.begin(), v.end() int mod = 1e9 + 7; const ll inf = 1e18; const int N = 1e6 + 50, K = 22; vector<bool> v; int n, m; vector<vector<pii>> a; vector<int> d, p, b; void dij(int u){ d.assign(n, inf); p.assign(n, -1); set<pii> q; q.insert({0, u}); d[u] = 0; while(!q.empty()){ int s = q.begin()->second; int di = q.begin()->first; q.erase(q.begin()); if(d[s] != di) continue; for(auto i : a[s]){ int to = i.first; int len = i.second; if(d[s] + len < d[to]){ d[to] = d[s] + len; p[to] = s; q.insert({d[to], to}); } } } } void solve(){ cin >> n >> m; a = vector<vector<pii>> (n); b = vector<int> (n, inf); v = vector<bool> (n, 0); while(m--){ int x, p; cin >> x >> p; if(x == 1) continue; b[x] = p; v[x] = 1; } v[1] = 1; for(int i = 0; i < n; i++){ for(int j = i + b[i]; j < n; j += b[i]) if(v[j]) a[i].push_back({j, (j - i) / b[i]}); for(int j = i - b[i]; j >= 0; j -= b[i]) if(v[j]) a[i].push_back({j, (i - j) / b[i]}); } dij(0); // for(auto i : d) // cout << i << ' '; // cout << '\n'; cout << (d[1] == inf ? -1 : d[1]) << '\n'; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while(t--) solve(); 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...