# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
838764 | 2023-08-27T17:32:09 Z | nonono | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 1000 ms | 27968 KB |
#include <bits/stdc++.h> using namespace std; const int INF = 1e8; const int mxN = 30005; int n, m; vector<vector<int>> adj(mxN); int b[mxN]; int f[mxN][200]; signed main() { #define taskname "" if(fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); cin >> n >> m; int N = sqrt(n); for(int i = 0; i < m; i ++) { int x, y; cin >> x >> y; adj[x].push_back(y); b[i] = x; } for(int i = 0; i < n; i ++) { for(int j = 0; j <= N; j ++) { f[i][j] = INF; } } priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq; f[b[0]][0] = 0; pq.push({0, b[0], 0}); while(!pq.empty()) { int u = pq.top()[1]; int d = pq.top()[0]; int k = pq.top()[2]; pq.pop(); if(d > f[u][k]) continue ; if(u == b[1]) { cout << d << "\n"; return 0; } for(int p : adj[u]) { if(p <= N) { for(int i : {-1, 1}) { int v = u + p * i; if(v >= 0 && v < n && f[v][p] > d + 1) { f[v][p] = d + 1; pq.push({f[v][p], v, p}); } } } else { for(int v = u % p; v < n; v += p) { if(f[v][0] > d + abs(u - v) / p) { f[v][0] = d + abs(u - v) / p; pq.push({f[v][0], v, 0}); } } } } if(k) { for(int i : {-1, 1}) { int v = u + k * i; if(v >= 0 && v < n && f[v][k] > d + 1) { f[v][k] = d + 1; pq.push({f[v][k], v, k}); } } } } cout << -1 << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 980 KB | Output is correct |
5 | Correct | 1 ms | 980 KB | Output is correct |
6 | Correct | 1 ms | 980 KB | Output is correct |
7 | Correct | 1 ms | 980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 980 KB | Output is correct |
5 | Correct | 1 ms | 980 KB | Output is correct |
6 | Correct | 1 ms | 980 KB | Output is correct |
7 | Correct | 1 ms | 980 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 980 KB | Output is correct |
10 | Correct | 1 ms | 1108 KB | Output is correct |
11 | Correct | 1 ms | 1108 KB | Output is correct |
12 | Correct | 1 ms | 1108 KB | Output is correct |
13 | Correct | 1 ms | 1108 KB | Output is correct |
14 | Correct | 1 ms | 1108 KB | Output is correct |
15 | Correct | 1 ms | 1108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 980 KB | Output is correct |
5 | Correct | 1 ms | 980 KB | Output is correct |
6 | Correct | 1 ms | 980 KB | Output is correct |
7 | Correct | 1 ms | 980 KB | Output is correct |
8 | Correct | 1 ms | 1028 KB | Output is correct |
9 | Correct | 1 ms | 980 KB | Output is correct |
10 | Correct | 1 ms | 1108 KB | Output is correct |
11 | Correct | 1 ms | 1108 KB | Output is correct |
12 | Correct | 1 ms | 1108 KB | Output is correct |
13 | Correct | 1 ms | 1108 KB | Output is correct |
14 | Correct | 2 ms | 1108 KB | Output is correct |
15 | Correct | 1 ms | 1108 KB | Output is correct |
16 | Correct | 1 ms | 1108 KB | Output is correct |
17 | Correct | 1 ms | 1620 KB | Output is correct |
18 | Correct | 1 ms | 2388 KB | Output is correct |
19 | Correct | 1 ms | 2516 KB | Output is correct |
20 | Correct | 2 ms | 2644 KB | Output is correct |
21 | Correct | 1 ms | 1364 KB | Output is correct |
22 | Correct | 1 ms | 2388 KB | Output is correct |
23 | Correct | 2 ms | 2260 KB | Output is correct |
24 | Correct | 2 ms | 2516 KB | Output is correct |
25 | Correct | 1 ms | 2644 KB | Output is correct |
26 | Correct | 1 ms | 2516 KB | Output is correct |
27 | Correct | 1 ms | 2516 KB | Output is correct |
28 | Correct | 2 ms | 2644 KB | Output is correct |
29 | Correct | 8 ms | 2644 KB | Output is correct |
30 | Correct | 2 ms | 2516 KB | Output is correct |
31 | Correct | 5 ms | 2644 KB | Output is correct |
32 | Correct | 3 ms | 2644 KB | Output is correct |
33 | Correct | 19 ms | 2772 KB | Output is correct |
34 | Correct | 14 ms | 2772 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 980 KB | Output is correct |
5 | Correct | 1 ms | 980 KB | Output is correct |
6 | Correct | 1 ms | 980 KB | Output is correct |
7 | Correct | 1 ms | 980 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 1104 KB | Output is correct |
10 | Correct | 1 ms | 1108 KB | Output is correct |
11 | Correct | 1 ms | 1108 KB | Output is correct |
12 | Correct | 1 ms | 1108 KB | Output is correct |
13 | Correct | 1 ms | 1108 KB | Output is correct |
14 | Correct | 1 ms | 1108 KB | Output is correct |
15 | Correct | 1 ms | 1108 KB | Output is correct |
16 | Correct | 1 ms | 1108 KB | Output is correct |
17 | Correct | 1 ms | 1620 KB | Output is correct |
18 | Correct | 1 ms | 2388 KB | Output is correct |
19 | Correct | 1 ms | 2516 KB | Output is correct |
20 | Correct | 1 ms | 2644 KB | Output is correct |
21 | Correct | 1 ms | 1364 KB | Output is correct |
22 | Correct | 1 ms | 2388 KB | Output is correct |
23 | Correct | 2 ms | 2260 KB | Output is correct |
24 | Correct | 2 ms | 2516 KB | Output is correct |
25 | Correct | 1 ms | 2644 KB | Output is correct |
26 | Correct | 1 ms | 2516 KB | Output is correct |
27 | Correct | 1 ms | 2516 KB | Output is correct |
28 | Correct | 2 ms | 2644 KB | Output is correct |
29 | Correct | 7 ms | 2644 KB | Output is correct |
30 | Correct | 3 ms | 2516 KB | Output is correct |
31 | Correct | 5 ms | 2644 KB | Output is correct |
32 | Correct | 3 ms | 2644 KB | Output is correct |
33 | Correct | 19 ms | 2772 KB | Output is correct |
34 | Correct | 14 ms | 2772 KB | Output is correct |
35 | Correct | 5 ms | 2516 KB | Output is correct |
36 | Correct | 2 ms | 1964 KB | Output is correct |
37 | Correct | 4 ms | 2900 KB | Output is correct |
38 | Correct | 7 ms | 3152 KB | Output is correct |
39 | Correct | 6 ms | 2900 KB | Output is correct |
40 | Correct | 5 ms | 2900 KB | Output is correct |
41 | Correct | 5 ms | 3028 KB | Output is correct |
42 | Correct | 4 ms | 2900 KB | Output is correct |
43 | Correct | 4 ms | 2900 KB | Output is correct |
44 | Correct | 5 ms | 2900 KB | Output is correct |
45 | Correct | 99 ms | 3028 KB | Output is correct |
46 | Correct | 78 ms | 3120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 980 KB | Output is correct |
5 | Correct | 1 ms | 980 KB | Output is correct |
6 | Correct | 1 ms | 980 KB | Output is correct |
7 | Correct | 1 ms | 980 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Correct | 1 ms | 980 KB | Output is correct |
10 | Correct | 1 ms | 1108 KB | Output is correct |
11 | Correct | 1 ms | 1108 KB | Output is correct |
12 | Correct | 1 ms | 1108 KB | Output is correct |
13 | Correct | 1 ms | 1108 KB | Output is correct |
14 | Correct | 1 ms | 1108 KB | Output is correct |
15 | Correct | 1 ms | 1108 KB | Output is correct |
16 | Correct | 1 ms | 1108 KB | Output is correct |
17 | Correct | 1 ms | 1620 KB | Output is correct |
18 | Correct | 1 ms | 2388 KB | Output is correct |
19 | Correct | 1 ms | 2516 KB | Output is correct |
20 | Correct | 2 ms | 2644 KB | Output is correct |
21 | Correct | 1 ms | 1364 KB | Output is correct |
22 | Correct | 1 ms | 2388 KB | Output is correct |
23 | Correct | 2 ms | 2260 KB | Output is correct |
24 | Correct | 2 ms | 2516 KB | Output is correct |
25 | Correct | 2 ms | 2664 KB | Output is correct |
26 | Correct | 1 ms | 2516 KB | Output is correct |
27 | Correct | 1 ms | 2516 KB | Output is correct |
28 | Correct | 2 ms | 2644 KB | Output is correct |
29 | Correct | 7 ms | 2644 KB | Output is correct |
30 | Correct | 2 ms | 2516 KB | Output is correct |
31 | Correct | 5 ms | 2644 KB | Output is correct |
32 | Correct | 3 ms | 2644 KB | Output is correct |
33 | Correct | 19 ms | 2772 KB | Output is correct |
34 | Correct | 14 ms | 2772 KB | Output is correct |
35 | Correct | 5 ms | 2516 KB | Output is correct |
36 | Correct | 2 ms | 2004 KB | Output is correct |
37 | Correct | 4 ms | 2900 KB | Output is correct |
38 | Correct | 6 ms | 3052 KB | Output is correct |
39 | Correct | 5 ms | 2900 KB | Output is correct |
40 | Correct | 5 ms | 2900 KB | Output is correct |
41 | Correct | 5 ms | 3028 KB | Output is correct |
42 | Correct | 4 ms | 2900 KB | Output is correct |
43 | Correct | 4 ms | 2900 KB | Output is correct |
44 | Correct | 4 ms | 2900 KB | Output is correct |
45 | Correct | 96 ms | 3028 KB | Output is correct |
46 | Correct | 77 ms | 3112 KB | Output is correct |
47 | Correct | 12 ms | 11668 KB | Output is correct |
48 | Correct | 12 ms | 19668 KB | Output is correct |
49 | Correct | 13 ms | 21428 KB | Output is correct |
50 | Correct | 13 ms | 23252 KB | Output is correct |
51 | Correct | 23 ms | 25752 KB | Output is correct |
52 | Correct | 23 ms | 25748 KB | Output is correct |
53 | Correct | 16 ms | 25172 KB | Output is correct |
54 | Correct | 12 ms | 24404 KB | Output is correct |
55 | Correct | 12 ms | 24404 KB | Output is correct |
56 | Correct | 18 ms | 25556 KB | Output is correct |
57 | Correct | 13 ms | 24532 KB | Output is correct |
58 | Correct | 18 ms | 24900 KB | Output is correct |
59 | Correct | 17 ms | 24788 KB | Output is correct |
60 | Correct | 17 ms | 24788 KB | Output is correct |
61 | Correct | 19 ms | 24788 KB | Output is correct |
62 | Correct | 42 ms | 25556 KB | Output is correct |
63 | Correct | 60 ms | 26696 KB | Output is correct |
64 | Correct | 68 ms | 26444 KB | Output is correct |
65 | Correct | 960 ms | 26444 KB | Output is correct |
66 | Execution timed out | 1071 ms | 27968 KB | Time limit exceeded |
67 | Halted | 0 ms | 0 KB | - |