Submission #1191938

#TimeUsernameProblemLanguageResultExecution timeMemory
1191938user192837Jakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1092 ms3600 KiB
#include <bits/stdc++.h> #define ar array #define all(x) x.begin(), x.end() using namespace std; typedef long long ll; const int N = 30005; const ll inf = 1e18; vector <int> g[N]; vector <ar <ll, 2>> e[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; int strt = -1, end = -1; for (int i = 0; i < m; i++) { int b, p; cin >> b >> p; if (i == 0) strt = b; else if (i == 1) end = b; g[b].push_back(p); } vector <ll> vis(n, inf); vis[strt] = 0; queue <int> q; q.push(strt); while (!q.empty()) { int x = q.front(); q.pop(); for (int p : g[x]) { int y = x, cnt = 1; while (y + p < n) { if (vis[y + p] > vis[x] + cnt) { vis[y + p] = vis[x] + cnt; q.push(y + p); } y += p, cnt++; } y = x, cnt = 1; while (y - p >= 0) { if (vis[y - p] > vis[x] + cnt) { vis[y - p] = vis[x] + cnt; q.push(y - p); } y -= p, cnt++; } } } if (vis[end] == inf) cout << -1; else cout << vis[end]; }
#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...