Submission #523142

#TimeUsernameProblemLanguageResultExecution timeMemory
523142vonatlusJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1078 ms33152 KiB
/// adil sultanov | vonat1us #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9 + 7; const int INF = 1e9 + 1e2; void fin() { #ifdef AM freopen(".in", "r", stdin); #endif } const bool flag = 0; const int M = 3e4+10; const int N = 2e3+10; int d[M]; vector<pii> adj[M]; void dijkstra(int m) { for (int i = 0; i < m; ++i) { d[i] = INF; } d[0] = 0; priority_queue<pii> q; q.push({0, 0}); while (!q.empty()) { auto [w, x] = q.top(); q.pop(); if (d[x] != -w) continue; for (auto [to, we] : adj[x]) { if (d[to] > d[x]+we) { d[to] = d[x]+we; q.push({-d[to], to}); } } } } void ma1n() { int n, m; cin >> n >> m; vector<int> b(m), p(m); for (int i = 0; i < m; ++i) { cin >> b[i] >> p[i]; } for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { if (i == j || b[j]%p[i] != b[i]%p[i]) continue; int dist = abs(b[j]-b[i])/p[i]; adj[i].pb({j, dist}); } } dijkstra(m); cout << (d[1] == INF ? -1 : d[1]); } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), fin(); int ts = 1; if (flag) { cin >> ts; } while (ts--) { ma1n(); } 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...