Submission #1202979

#TimeUsernameProblemLanguageResultExecution timeMemory
1202979rshohruhJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms2376 KiB
// author: rshohruh #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #ifdef LOCAL #include "debug.hpp" #else #define debug(...) 42 #endif using namespace std; #define int long long #define inf 1e18 const int MXN = 3e4 + 5; int b[MXN], p[MXN], dist[MXN]; vector<int> g[MXN]; map<int, int> mp[MXN]; // #define with_testcases void t_main(){ int n, m; cin >> n >> m; for (int i = 0; i < n; i++) dist[i] = inf; for (int i = 0; i < m; i++) { cin >> b[i] >> p[i]; g[b[i]].push_back(p[i]); } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[b[0]] = 0; pq.push({0, b[0]}); while (!pq.empty()) { auto [k, u] = pq.top(); pq.pop(); if (dist[u] != inf) continue; for (int v : g[u]) { // if (mp[v].find(u) != mp[v].end()) continue; // mp[v][u]; for (int i = u - v, t = 1; i >= 0; i -= v, ++t) { if (dist[i] > dist[u] + t) { dist[i] = dist[u] + t; pq.push({dist[i], i}); } } for (int i = u + v, t = 1; i < n; i += v, ++t) { if (dist[i] > dist[u] + t) { dist[i] = dist[u] + t; pq.push({dist[i], i}); } } } } cout << (dist[b[1]] >= inf ? -1 : dist[b[1]]) << '\n'; } signed main(){ signed t = 1; cin.tie(nullptr)->sync_with_stdio(false); #ifdef with_testcases cin >> t; #endif while(t--){ t_main(); cout << '\n'; } 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...