# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
238124 | 2020-06-10T01:48:15 Z | HellAngel | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 7 ms | 1664 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); } if(m == 1) { cout << -1; return 0; } dist[start[1]] = 0; pq.emplace(0, start[1]); 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]) { int cnt = 0; for(int i = 1;;i++) { int nxt = u + i * len[j]; bool ok = 0; bool sure = 0; ok |= Inside(nxt); if(Inside(nxt) && dist[nxt] > dist[u] + i) { sure = 1; 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) { sure = 1; dist[nxt] = dist[u] + i; pq.emplace(dist[nxt], nxt); } if(!sure) { cnt++; if(cnt >= 100) break; } else cnt = 0; if(!ok) break; } } } cout << -1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 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 | 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1536 KB | Output is correct |
2 | Correct | 6 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 | 5 ms | 1536 KB | Output is correct |
7 | Correct | 5 ms | 1536 KB | Output is correct |
8 | Correct | 6 ms | 1536 KB | Output is correct |
9 | Correct | 5 ms | 1536 KB | Output is correct |
10 | Correct | 6 ms | 1536 KB | Output is correct |
11 | Correct | 5 ms | 1536 KB | Output is correct |
12 | Correct | 5 ms | 1536 KB | Output is correct |
13 | Correct | 6 ms | 1536 KB | Output is correct |
14 | Correct | 5 ms | 1536 KB | Output is correct |
15 | 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 | 6 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 | 6 ms | 1536 KB | Output is correct |
6 | Correct | 6 ms | 1536 KB | Output is correct |
7 | Correct | 6 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 1536 KB | Output is correct |
9 | Correct | 5 ms | 1536 KB | Output is correct |
10 | Correct | 6 ms | 1536 KB | Output is correct |
11 | Correct | 6 ms | 1536 KB | Output is correct |
12 | Correct | 5 ms | 1536 KB | Output is correct |
13 | Correct | 6 ms | 1536 KB | Output is correct |
14 | Correct | 6 ms | 1536 KB | Output is correct |
15 | Correct | 5 ms | 1536 KB | Output is correct |
16 | Correct | 6 ms | 1568 KB | Output is correct |
17 | Correct | 6 ms | 1536 KB | Output is correct |
18 | Correct | 5 ms | 1536 KB | Output is correct |
19 | Correct | 6 ms | 1536 KB | Output is correct |
20 | Correct | 6 ms | 1664 KB | Output is correct |
21 | Correct | 6 ms | 1536 KB | Output is correct |
22 | Correct | 5 ms | 1664 KB | Output is correct |
23 | Correct | 6 ms | 1664 KB | Output is correct |
24 | Correct | 6 ms | 1664 KB | Output is correct |
25 | Correct | 6 ms | 1536 KB | Output is correct |
26 | Correct | 6 ms | 1536 KB | Output is correct |
27 | Correct | 6 ms | 1536 KB | Output is correct |
28 | Incorrect | 6 ms | 1664 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1536 KB | Output is correct |
2 | Correct | 6 ms | 1536 KB | Output is correct |
3 | Correct | 6 ms | 1536 KB | Output is correct |
4 | Correct | 6 ms | 1536 KB | Output is correct |
5 | Correct | 6 ms | 1536 KB | Output is correct |
6 | Correct | 6 ms | 1536 KB | Output is correct |
7 | Correct | 6 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 1536 KB | Output is correct |
9 | Correct | 5 ms | 1664 KB | Output is correct |
10 | Correct | 5 ms | 1536 KB | Output is correct |
11 | Correct | 6 ms | 1536 KB | Output is correct |
12 | Correct | 5 ms | 1536 KB | Output is correct |
13 | Correct | 6 ms | 1536 KB | Output is correct |
14 | Correct | 6 ms | 1536 KB | Output is correct |
15 | Correct | 6 ms | 1536 KB | Output is correct |
16 | Correct | 5 ms | 1536 KB | Output is correct |
17 | Correct | 6 ms | 1536 KB | Output is correct |
18 | Correct | 6 ms | 1536 KB | Output is correct |
19 | Correct | 5 ms | 1536 KB | Output is correct |
20 | Correct | 7 ms | 1664 KB | Output is correct |
21 | Correct | 5 ms | 1536 KB | Output is correct |
22 | Correct | 6 ms | 1536 KB | Output is correct |
23 | Correct | 6 ms | 1536 KB | Output is correct |
24 | Correct | 6 ms | 1664 KB | Output is correct |
25 | Correct | 6 ms | 1536 KB | Output is correct |
26 | Correct | 6 ms | 1536 KB | Output is correct |
27 | Correct | 7 ms | 1536 KB | Output is correct |
28 | Incorrect | 6 ms | 1664 KB | Output isn't correct |
29 | 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 | 6 ms | 1536 KB | Output is correct |
7 | Correct | 5 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 1536 KB | Output is correct |
9 | Correct | 6 ms | 1536 KB | Output is correct |
10 | Correct | 5 ms | 1536 KB | Output is correct |
11 | Correct | 5 ms | 1536 KB | Output is correct |
12 | Correct | 6 ms | 1664 KB | Output is correct |
13 | Correct | 7 ms | 1536 KB | Output is correct |
14 | Correct | 6 ms | 1536 KB | Output is correct |
15 | Correct | 5 ms | 1536 KB | Output is correct |
16 | Correct | 6 ms | 1664 KB | Output is correct |
17 | Correct | 6 ms | 1536 KB | Output is correct |
18 | Correct | 5 ms | 1536 KB | Output is correct |
19 | Correct | 6 ms | 1536 KB | Output is correct |
20 | Correct | 6 ms | 1664 KB | Output is correct |
21 | Correct | 5 ms | 1536 KB | Output is correct |
22 | Correct | 5 ms | 1536 KB | Output is correct |
23 | Correct | 6 ms | 1664 KB | Output is correct |
24 | Correct | 6 ms | 1664 KB | Output is correct |
25 | Correct | 6 ms | 1536 KB | Output is correct |
26 | Correct | 5 ms | 1536 KB | Output is correct |
27 | Correct | 6 ms | 1664 KB | Output is correct |
28 | Incorrect | 6 ms | 1664 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |