제출 #1128873

#제출 시각아이디문제언어결과실행 시간메모리
1128873belgianbotJakarta Skyscrapers (APIO15_skyscraper)C++20
36 / 100
1096 ms1332 KiB
/* AUTHOR : BELGIANBOT */ #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<typename T> void read(T& x) { cin >> x;} template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);} template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); } template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); } template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); } template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); } template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; } #define pb push_back #define fi first #define se second #define ordered_set tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define mp make_pair #define sz(x) (int)(x.size()) #define YES cout<<"YES\n"; #define Yes cout<<"Yes\n"; #define NO cout<<"NO\n"; #define No cout << "No\n"; #define cmin(a, b) a = min(a, b) #define cmax(a, b) a = max(a, b) //#define int long long #define double long double const int inf = numeric_limits<int>::max() / 4; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MOD = 1e9+7, LOG=20; void solve(); signed main() { ios::sync_with_stdio(false); int t = 1; //cin >> t; while (t--) solve(); return 0; } vector<int> memo, b, p; int n, m; void solve() { cin >> n >> m; b.clear(); p.clear(); b.resize(m); p.resize(m); for (int i = 0; i < m; i++) { cin >> b[i] >> p[i]; } if (b[0] == b[1]) { cout << "0\n"; return; } priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; q.push({0,0}); vector<int> dist(m, inf); dist[0] = 0; vector<bool> processed(m, false); while(!q.empty()) { auto [u,v] = q.top(); q.pop(); if (processed[v]) continue; processed[v] = true; for (int i = 1; i < m; i++) { if (i == v) continue; if (abs(b[i] - b[v]) % p[v] == 0) { if (dist[i] > dist[v] + abs(b[i] - b[v]) / p[v]) { dist[i] = dist[v] + abs(b[i] - b[v]) / p[v]; if (i!=1)q.push({dist[i], i}); } } } } cout << (dist[1] == inf ? -1 : dist[1]) << '\n'; }
#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...