Submission #41497

#TimeUsernameProblemLanguageResultExecution timeMemory
41497cmasterJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
292 ms19332 KiB
#include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp>*/ #define pb push_back #define mp make_pair #define sz(s) ((int)(s.size())) #define all(s) s.begin(), s.end() #define rep(i, a, n) for (int i = a; i <= n; ++i) #define per(i, n, a) for (int i = n; i >= a; --i) #define onlycin ios_base::sync_with_stdio(false); cin.tie(0) #define F first #define S second using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; /*typedef tree< pair < int, int >, null_type, less< pair < int, int > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;*/ // find_by_order() order_of_key() const int MAXN = (int)5e5+228; const char nxtl = '\n'; const int mod = (int)1e9+7; const double eps = (double)1e-7; template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;} template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;} int n, m, b[MAXN], p[MAXN], d[MAXN]; vector < int > have[MAXN]; int main() { #ifdef accepted freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif onlycin; cin >> n >> m; rep(i, 1, m) { cin >> b[i] >> p[i]; have[++b[i]].pb(p[i]); } rep(i, 1, n) { sort(all(have[i])); have[i].resize(unique(all(have[i]))-have[i].begin()); } memset(d, 0x3f, sizeof d); d[b[1]] = 0; set < pair < int, int > > S; S.insert(mp(0, b[1])); while(!S.empty()) { int v = S.begin()->second; S.erase(S.begin()); for(auto &to : have[v]) { int cnt = 0; for(int go = v + to; go <= n; go += to) { cnt++; if(cnt + d[v] < d[go]) { S.erase(mp(d[go], go)); d[go] = d[v]+cnt; S.insert(mp(d[go], go)); } if(binary_search(all(have[go]), to)) break; } cnt = 0; for(int go = v - to; go > 0; go -= to) { cnt++; if(cnt + d[v] < d[go]) { S.erase(mp(d[go], go)); d[go] = d[v]+cnt; S.insert(mp(d[go], go)); } if(binary_search(all(have[go]), to)) break; } } } if(d[b[2]] == d[0]) d[b[2]] = -1; cout << d[b[2]] << nxtl; 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...