Submission #389645

#TimeUsernameProblemLanguageResultExecution timeMemory
389645milleniumEeeeJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
252 ms262148 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); #define int long long using namespace std; const int MAXN = (int)2e5 + 5; const int INF = 1e18; int pos[MAXN], p[MAXN]; vector <pii> g[MAXN]; int n, m; void create(int pos, int x) { if (x == 0) { // wtf return; } for (int i = pos % x; i < n; i += x) { if (i != pos && 0 <= i && i < n) { g[pos].pb({abs(pos - i) / x, i}); } } } int dist[MAXN]; signed main() { fastInp; cin >> n >> m; for (int i = 0; i < m; i++) { cin >> pos[i] >> p[i]; create(pos[i], p[i]); } //for (int i = 1; i <= 1e5; i++) { //cerr << "ok" << endl; //} memset(dist, -1, sizeof(dist)); dist[pos[0]] = 0; queue <pii> pq; pq.push({0, pos[0]}); while (!pq.empty()) { int v = pq.front().sc; int cost = -pq.front().fr; pq.pop(); if (cost > dist[v]) { continue; } for (auto el : g[v]) { int c = el.fr, to = el.sc; if (dist[to] == -1 || dist[to] > dist[v] + c) { dist[to] = dist[v] + c; pq.push({-dist[to], to}); } } } cout << dist[pos[1]] << endl; } /* 4 4 1 1 0 1 3 4 2 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...