제출 #1275802

#제출 시각아이디문제언어결과실행 시간메모리
1275802nariman_mt87Jakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
1096 ms4284 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define lli long long int #define pii pair<lli,lli> #define all(x) x.begin(),x.end() #define mk make_pair #define pb push_back #define se second #define fi first #define nn '\n' #define txt freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); #define T int T;cin>>T;while(T--) #define ashar(x) fixed<<setprecision(x) #define migmig ios_base::sync_with_stdio(0);cin.tie(0); const int maxn= 1e6 + 1, mod = 1e6 + 3; lli pwm(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pwm(a * a , b / 2) : pwm(a * a, b / 2))); } lli pw(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pw(a * a % mod, b / 2) % mod : pw(a * a % mod, b / 2) % mod)); }//a*pw(b,mod-2) == (a/b)%mod lli n, m, k; lli h[maxn], b[maxn]; vector<lli> e[maxn]; bool vis[maxn]; void dij(lli s){ h[s] = 0; priority_queue<pii, vector<pii>, greater<pii>> q; q.push({0, s}); while(!q.empty()){ lli v = q.top().se, w = q.top().fi; q.pop(); if(vis[v]) continue; vis[v] = 1; for(auto x : e[v]){ lli l = 1; for(int i = v; i + x < n; i += x){ if(w + l < h[i + x]){ h[i + x] = w + l; q.push({h[i + x], i + x}); } l++; } l = 1; for(int i = v; i - x >= 0; i -= x){ if(w + l < h[i - x]){ h[i - x] = w + l; q.push({h[i - x], i - x}); } l++; } } } } int main(){ migmig; cin >> n >> m; lli x, y; for(int i = 0; i < m; i++){ cin >> b[i] >> y; e[b[i]].pb(y); } fill(h, h + n + 1, 1e9); dij(b[0]); //for(int i = 0; i < n; i ++) cerr << h[i] << " "; cout << (h[b[1]] == 1e9 ? -1 : h[b[1]]) << nn; }
#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...