# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
238136 | 2020-06-10T02:00:15 Z | HellAngel | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 1000 ms | 3704 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(len[i]); } for(int i = 0; i < n; i++) { sort(pos[i].begin(), pos[i].end()); pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end()); reverse(pos[i].begin(), pos[i].end()); } 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 * 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 * 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++; } else cnt = 0; if(cnt >= 15000) break; 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 | 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 | 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 | 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 | 5 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 | 5 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 | 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 |
# | 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 | 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 | 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 | 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 | 5 ms | 1536 KB | Output is correct |
17 | Correct | 6 ms | 1664 KB | Output is correct |
18 | Correct | 5 ms | 1584 KB | Output is correct |
19 | Correct | 5 ms | 1536 KB | Output is correct |
20 | Correct | 13 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 | 1536 KB | Output is correct |
24 | Correct | 7 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 | Correct | 6 ms | 1664 KB | Output is correct |
29 | Correct | 7 ms | 1664 KB | Output is correct |
30 | Correct | 6 ms | 1664 KB | Output is correct |
31 | Correct | 6 ms | 1664 KB | Output is correct |
32 | Correct | 6 ms | 1664 KB | Output is correct |
33 | Correct | 8 ms | 1664 KB | Output is correct |
34 | Correct | 8 ms | 1664 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 | 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 | 5 ms | 1536 KB | Output is correct |
13 | Correct | 5 ms | 1536 KB | Output is correct |
14 | Correct | 5 ms | 1536 KB | Output is correct |
15 | Correct | 8 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 | 5 ms | 1536 KB | Output is correct |
19 | Correct | 5 ms | 1536 KB | Output is correct |
20 | Correct | 14 ms | 1664 KB | Output is correct |
21 | Correct | 6 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 | 7 ms | 1536 KB | Output is correct |
26 | Correct | 5 ms | 1536 KB | Output is correct |
27 | Correct | 6 ms | 1536 KB | Output is correct |
28 | Correct | 6 ms | 1664 KB | Output is correct |
29 | Correct | 6 ms | 1664 KB | Output is correct |
30 | Correct | 6 ms | 1664 KB | Output is correct |
31 | Correct | 6 ms | 1664 KB | Output is correct |
32 | Correct | 6 ms | 1664 KB | Output is correct |
33 | Correct | 7 ms | 1664 KB | Output is correct |
34 | Correct | 6 ms | 1664 KB | Output is correct |
35 | Correct | 12 ms | 2048 KB | Output is correct |
36 | Correct | 6 ms | 1664 KB | Output is correct |
37 | Correct | 11 ms | 1920 KB | Output is correct |
38 | Correct | 15 ms | 2048 KB | Output is correct |
39 | Correct | 12 ms | 2048 KB | Output is correct |
40 | Correct | 14 ms | 2048 KB | Output is correct |
41 | Correct | 12 ms | 2176 KB | Output is correct |
42 | Correct | 11 ms | 2048 KB | Output is correct |
43 | Correct | 10 ms | 2048 KB | Output is correct |
44 | Correct | 19 ms | 2048 KB | Output is correct |
45 | Correct | 13 ms | 2048 KB | Output is correct |
46 | Correct | 14 ms | 2048 KB | Output is correct |
# | 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 | 1456 KB | Output is correct |
7 | Correct | 5 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 | 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 | 5 ms | 1536 KB | Output is correct |
14 | Correct | 5 ms | 1536 KB | Output is correct |
15 | Correct | 5 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 | 5 ms | 1536 KB | Output is correct |
19 | Correct | 5 ms | 1536 KB | Output is correct |
20 | Correct | 13 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 | 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 | 5 ms | 1536 KB | Output is correct |
27 | Correct | 6 ms | 1536 KB | Output is correct |
28 | Correct | 6 ms | 1536 KB | Output is correct |
29 | Correct | 7 ms | 1664 KB | Output is correct |
30 | Correct | 7 ms | 1664 KB | Output is correct |
31 | Correct | 6 ms | 1664 KB | Output is correct |
32 | Correct | 6 ms | 1664 KB | Output is correct |
33 | Correct | 7 ms | 1664 KB | Output is correct |
34 | Correct | 7 ms | 1664 KB | Output is correct |
35 | Correct | 12 ms | 2048 KB | Output is correct |
36 | Correct | 6 ms | 1664 KB | Output is correct |
37 | Correct | 10 ms | 1920 KB | Output is correct |
38 | Correct | 12 ms | 2048 KB | Output is correct |
39 | Correct | 12 ms | 2048 KB | Output is correct |
40 | Correct | 11 ms | 2048 KB | Output is correct |
41 | Correct | 12 ms | 2048 KB | Output is correct |
42 | Correct | 10 ms | 2048 KB | Output is correct |
43 | Correct | 11 ms | 2048 KB | Output is correct |
44 | Correct | 18 ms | 2048 KB | Output is correct |
45 | Correct | 14 ms | 2048 KB | Output is correct |
46 | Correct | 13 ms | 2048 KB | Output is correct |
47 | Correct | 16 ms | 2812 KB | Output is correct |
48 | Correct | 12 ms | 2176 KB | Output is correct |
49 | Correct | 12 ms | 2176 KB | Output is correct |
50 | Correct | 9 ms | 2048 KB | Output is correct |
51 | Correct | 22 ms | 3704 KB | Output is correct |
52 | Correct | 22 ms | 3068 KB | Output is correct |
53 | Correct | 15 ms | 2688 KB | Output is correct |
54 | Correct | 7 ms | 1920 KB | Output is correct |
55 | Correct | 7 ms | 1920 KB | Output is correct |
56 | Execution timed out | 1096 ms | 3200 KB | Time limit exceeded |
57 | Halted | 0 ms | 0 KB | - |