Submission #544549

#TimeUsernameProblemLanguageResultExecution timeMemory
544549SavicSJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
358 ms30512 KiB
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <bits/stdc++.h> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pdd; #define ff(i,a,b) for(int i = a; i <= b; i++) #define fb(i,b,a) for(int i = b; i >= a; i--) #define trav(a,x) for (auto& a : x) #define sz(a) (int)(a).size() #define pb push_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // os.order_of_key(k) the number of elements in the os less than k // *os.find_by_order(k) print the k-th smallest number in os(0-based) const int mod = 1000000007; const ll inf = 1e15 + 5; const int mxN = 30005; int n, m; int B[mxN]; int P[mxN]; vector<pii> g[mxN]; ll dist[mxN]; map<int,int> mp[mxN]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> m >> n; ff(i,0,n - 1)cin >> B[i] >> P[i]; int S = B[0]; int T = B[1]; ff(i,0,n - 1){ int pos = B[i] + P[i], cost = 1; while(pos < m){ g[B[i]].pb({pos, cost}); cost += 1; if(mp[pos].count(P[i]) == 1)break; mp[pos][P[i]] = 1; pos += P[i]; } } ff(i,0,m - 1)mp[i].clear(); ff(i,0,n - 1){ int pos = B[i] - P[i], cost = 1; while(pos >= 0){ g[B[i]].pb({pos, cost}); cost += 1; if(mp[pos].count(P[i]) == 1)break; mp[pos][P[i]] = 1; pos -= P[i]; } } ff(i,0,m - 1)dist[i] = inf; priority_queue<pll, vector<pll>, greater<pll>> pq; pq.push({dist[S] = 0, S}); while(sz(pq)){ pll v = pq.top(); pq.pop(); if(dist[v.se] < v.fi)continue; for(auto c : g[v.se]){ int u = c.fi; int w = c.se; if(dist[u] > v.fi + w){ pq.push({dist[u] = v.fi + w, u}); } } } cout << (dist[T] == inf ? -1 : dist[T]) << '\n'; return 0; } /* 5 3 0 2 1 1 4 1 // probati bojenje sahovski */
#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...