제출 #1275754

#제출 시각아이디문제언어결과실행 시간메모리
1275754itsKiaRashJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms572 KiB
#include <bits/stdc++.h> using namespace std; // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/pb_ds/assoc_container.hpp> // using namespace __gnu_pbds; // find_by_order order_of_key // template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; // #pragma GCC optimize ("O2,unroll-loops") // #pragma GCC optimize ("Ofast") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #define int ll #define FAST_IO (ios_base::sync_with_stdio(false), cin.tie(NULL)); #define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define testc int ttt;cin>>ttt;while(ttt--) #define alll(x) (x).begin(),(x).end() #define pqi priority_queue<pii, vector<pii>, greater<pii>> #define endl '\n' #define pb push_back #define ins insert #define pii pair<int, int> #define ff first #define ss second #define bg begin #define rbg rbegin #define sz size() #define mset(x,y) memset(x,y,sizeof(x)) #define clr clear() #define YES cout<<"YES"<<endl #define NO cout<<"NO"<<endl #define vci vector<int> #define sti set<int> #define nl cout<<'\n' #define upb upper_bound #define lrb lower_bound //ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);} ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); } const ll inf = 1e9 + 18; const int maxn = 3e4 + 7, mod = 1e9 + 7; //998244353 return ans;} int n, m; int b[maxn], p[maxn], val[maxn]; vci adj[maxn]; queue<int> q; // void dij(int a){ // fill(val, val + n + 1, inf); // val[a] = 0; // pqi pq; pq.push({0, a}); // while(pq.sz){ // auto[ww, u] = pq.top(); pq.pop(); // if(ww > val[u]) continue; // for(auto[w, v] : adj[u]){ // if(val[u] + w < val[v]){ // val[v] = val[u] + w; // pq.push({val[v], v}); // } // } // } // } int32_t main() { FAST_IO cin >> n >> m ; for(int i = 0 ; i < m ; i ++){ cin >> b[i] >> p[i]; adj[b[i]].pb(i); } q.push(0); //dij(0); fill(val, val + m, inf); val[0] = 0; while (q.sz){ int x = q.front(); q.pop(); int d = 0; for(int i = b[x] ; i >= 0 ; i -= p[x]){ for(int item : adj[i]){ if(val[x] + d < val[item]){ val[item] = val[x] + d; q.push(item); } } d ++; } d = 0; for(int i = b[x] + p[x] ; i < n ; i += p[x]){ for(int item : adj[i]){ if(val[x] + d < val[item]){ val[item] = val[x] + d; q.push(item); } } d ++; } } if (val[1] >= inf) cout << -1 << endl; else cout << val[1] << endl; 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...