Submission #495660

#TimeUsernameProblemLanguageResultExecution timeMemory
495660vishesh312Jakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms316 KiB
#include "bits/stdc++.h" using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; */ #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)(x).size() using ll = long long; const int mod = 1e9+7; void solve(int tc) { int n, m; cin >> n >> m; vector<set<int>> ju(n); set<int> p; vector<vector<pair<int, int>>> adj(n); while (m--) { int a, b; cin >> a >> b; ju[a].insert(b); p.insert(b); } for (int i = 0; i < n; ++i) { for (int x : ju[i]) { int cur = i; while (cur+x < n) { cur += x; adj[i].push_back({cur, (cur-i)/x}); if (ju[cur].count(x)) break; } cur = i; while (cur-x >= 0) { cur -= x; adj[i].push_back({cur, (i-cur)/x}); if (ju[cur].count(x)) break; } } } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, 0}); vector<int> dist(n, (1<<30)); dist[0] = 0; while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] < d) continue; for (auto [v, dd] : adj[u]) { if (dist[v] < dist[u]+dd) continue; dist[v] = dist[u] + dd; pq.push({dist[v], v}); } } cout << dist[1] << '\n'; } signed main() { cin.tie(0)->sync_with_stdio(0); int tc = 1; //cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); 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...