Submission #107908

#TimeUsernameProblemLanguageResultExecution timeMemory
107908dfistricJakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
533 ms263168 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define ll long long using namespace std; const int MAXN = 30010; int B[MAXN], P[MAXN]; int n, m; vector <pair <int, int> > ve[MAXN]; set <pair <int, int> > se; int dist[MAXN]; int bio[MAXN]; vector <int> E[MAXN]; int main() { ios_base::sync_with_stdio(false); cin >> n >> m; REP(i, m) cin >> B[i] >> P[i]; REP(i, m) { REP(j, n) { if (abs(B[i] - j) % P[i] == 0) ve[B[i]].push_back({j, abs(B[i] - j) / P[i]}); } } REP(i, n) dist[i] = 1e9; dist[B[0]] = 0; REP(i, n) se.insert({dist[i], i}); while (se.size()) { auto tr = *se.begin(); se.erase(se.begin()); int x = tr.second, D = tr.first; bio[x] = 1; if (x == B[1]) continue; for (auto t : ve[x]) { int y = t.first, d = t.second; if (dist[y] > D + d) { assert(bio[y] == 0); se.erase({dist[y], y}); dist[y] = D + d; se.insert({dist[y], y}); } } } if (dist[B[1]] >= 1e9) cout << "-1\n"; else cout << dist[B[1]] << "\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...