# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
238120 | 2020-06-10T01:44:38 Z | HellAngel | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 6 ms | 1568 KB |
#include <bits/stdc++.h> using namespace std; const int maxn = 50007; int n, m, a[maxn], start[maxn], len[maxn], dist[maxn]; vector<int> pos[maxn]; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; bool Inside(int x) { return (x >= 0 && x < n); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout); cin >> n >> m; fill_n(dist, n, 1e9); for(int i = 1; i <= m; i++) { cin >> start[i] >> len[i]; pos[start[i]].push_back(i); } dist[start[1]] = 0; pq.emplace(0, 0); while(pq.size()) { pair<int, int> p = pq.top(); pq.pop(); if(p.first != dist[p.second]) continue; int u = p.second; if(u == start[2]) { cout << p.first; exit(0); } for(auto j: pos[u]) { for(int i = 1;;i++) { int nxt = u + i * len[j]; bool ok = 0; ok |= Inside(nxt); if(Inside(nxt) && dist[nxt] > dist[u] + i) { dist[nxt] = dist[u] + i; pq.emplace(dist[nxt], nxt); } nxt = u - i * len[j]; ok |= Inside(nxt); if(Inside(nxt) && dist[nxt] > dist[u] + i) { dist[nxt] = dist[u] + i; pq.emplace(dist[nxt], nxt); } if(!ok) break; } } } cout << -1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1536 KB | Output is correct |
2 | Correct | 5 ms | 1408 KB | Output is correct |
3 | Correct | 5 ms | 1536 KB | Output is correct |
4 | Correct | 6 ms | 1536 KB | Output is correct |
5 | Correct | 5 ms | 1536 KB | Output is correct |
6 | Correct | 5 ms | 1536 KB | Output is correct |
7 | Correct | 6 ms | 1536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1536 KB | Output is correct |
2 | Correct | 5 ms | 1536 KB | Output is correct |
3 | Correct | 5 ms | 1568 KB | Output is correct |
4 | Correct | 5 ms | 1536 KB | Output is correct |
5 | Correct | 5 ms | 1536 KB | Output is correct |
6 | Correct | 5 ms | 1536 KB | Output is correct |
7 | Correct | 5 ms | 1536 KB | Output is correct |
8 | Incorrect | 5 ms | 1536 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1536 KB | Output is correct |
2 | Correct | 5 ms | 1536 KB | Output is correct |
3 | Correct | 6 ms | 1536 KB | Output is correct |
4 | Correct | 5 ms | 1536 KB | Output is correct |
5 | Correct | 5 ms | 1536 KB | Output is correct |
6 | Correct | 6 ms | 1536 KB | Output is correct |
7 | Correct | 5 ms | 1536 KB | Output is correct |
8 | Incorrect | 5 ms | 1536 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1536 KB | Output is correct |
2 | Correct | 6 ms | 1536 KB | Output is correct |
3 | Correct | 5 ms | 1536 KB | Output is correct |
4 | Correct | 6 ms | 1536 KB | Output is correct |
5 | Correct | 5 ms | 1536 KB | Output is correct |
6 | Correct | 6 ms | 1536 KB | Output is correct |
7 | Correct | 5 ms | 1536 KB | Output is correct |
8 | Incorrect | 6 ms | 1536 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1536 KB | Output is correct |
2 | Correct | 5 ms | 1536 KB | Output is correct |
3 | Correct | 5 ms | 1536 KB | Output is correct |
4 | Correct | 5 ms | 1536 KB | Output is correct |
5 | Correct | 5 ms | 1536 KB | Output is correct |
6 | Correct | 5 ms | 1536 KB | Output is correct |
7 | Correct | 5 ms | 1536 KB | Output is correct |
8 | Incorrect | 5 ms | 1536 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |