# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
709885 | 2023-03-14T18:34:47 Z | noedit | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 1000 ms | 191688 KB |
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; const int INF = 1e9; const int B = 90; const int MAXN = 3e4 + 5; vector<pair<int, int> > d; int dist[MAXN][B]; vector<array<short, 3> > g[MAXN][B]; signed main() { //ifstream cin("input.txt"); //ofstream cout("output.txt"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; d.resize(m); vector<int> big; for (int i = 0; i < m; i++) { cin >> d[i].first >> d[i].second; if (d[i].second >= B) { big.push_back(i); } } for (int i = 0; i < n; i++) for (int j = 0; j < B; j++) dist[i][j] = INF; for (int i = 0; i < m; i++) { if (d[i].second >= B) continue; g[d[i].first][0].push_back({d[i].first, d[i].second, 0}); } for (int i = 0; i < n; i++) { for (int j = 1; j < B; j++) { if (i - j >= 0) { g[i][j].push_back({i - j, 0, 1}); g[i][j].push_back({i - j, j, 1}); } if (i + j < n) { g[i][j].push_back({i + j, 0, 1}); g[i][j].push_back({i + j, j, 1}); } } } for (auto& i : big) { for (int j = d[i].first, k = 0; j < n; j += d[i].second, k++) { g[d[i].first][0].push_back({j, 0, k}); } for (int j = d[i].first, k = 0; j >= 0; j -= d[i].second, k++) { g[d[i].first][0].push_back({j, 0, k}); } } set<array<int, 3> > st; st.insert({0, d[0].first, 0}); dist[d[0].first][0] = 0; while (!st.empty()) { auto [dst, pos, pw] = *st.begin(); st.erase(st.begin()); if (dst > dist[pos][pw]) continue; for (auto& [psu, pwu, w] : g[pos][pw]) { if (dist[psu][pwu] > dst + w) { st.erase({dist[psu][pwu], psu, pwu}); dist[psu][pwu] = dst + w; st.insert({dist[psu][pwu], psu, pwu}); } } } int mn = INF; for (int i = 0; i < B; i++) mn = min(mn, dist[d[1].first][i]); if (mn == INF) cout << -1; else cout << mn; return 0; } /* small (i, j) -1> (i - j, 0), (i + j, 0) (i, 0) -0> (i, j) (i, j) -1> (i - j, j), (i + j, j) large (i, 0) -1> (i + j, 0) (i, 0) -1> (i - j, 0) */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 63700 KB | Output is correct |
2 | Correct | 31 ms | 63700 KB | Output is correct |
3 | Correct | 31 ms | 63724 KB | Output is correct |
4 | Correct | 32 ms | 63700 KB | Output is correct |
5 | Correct | 32 ms | 63620 KB | Output is correct |
6 | Correct | 33 ms | 63744 KB | Output is correct |
7 | Correct | 31 ms | 63692 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 63696 KB | Output is correct |
2 | Correct | 32 ms | 63692 KB | Output is correct |
3 | Correct | 32 ms | 63632 KB | Output is correct |
4 | Correct | 34 ms | 63716 KB | Output is correct |
5 | Correct | 32 ms | 63692 KB | Output is correct |
6 | Correct | 32 ms | 63656 KB | Output is correct |
7 | Correct | 32 ms | 63728 KB | Output is correct |
8 | Correct | 33 ms | 63764 KB | Output is correct |
9 | Correct | 35 ms | 63784 KB | Output is correct |
10 | Correct | 36 ms | 64084 KB | Output is correct |
11 | Correct | 34 ms | 64084 KB | Output is correct |
12 | Correct | 33 ms | 63956 KB | Output is correct |
13 | Correct | 35 ms | 63956 KB | Output is correct |
14 | Correct | 36 ms | 64092 KB | Output is correct |
15 | Correct | 38 ms | 64116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 63700 KB | Output is correct |
2 | Correct | 40 ms | 63624 KB | Output is correct |
3 | Correct | 34 ms | 63608 KB | Output is correct |
4 | Correct | 36 ms | 63676 KB | Output is correct |
5 | Correct | 34 ms | 63688 KB | Output is correct |
6 | Correct | 37 ms | 63656 KB | Output is correct |
7 | Correct | 34 ms | 63660 KB | Output is correct |
8 | Correct | 32 ms | 63784 KB | Output is correct |
9 | Correct | 34 ms | 63796 KB | Output is correct |
10 | Correct | 35 ms | 64008 KB | Output is correct |
11 | Correct | 34 ms | 64080 KB | Output is correct |
12 | Correct | 33 ms | 63980 KB | Output is correct |
13 | Correct | 35 ms | 63992 KB | Output is correct |
14 | Correct | 36 ms | 64096 KB | Output is correct |
15 | Correct | 37 ms | 64136 KB | Output is correct |
16 | Correct | 34 ms | 64348 KB | Output is correct |
17 | Correct | 42 ms | 66176 KB | Output is correct |
18 | Correct | 54 ms | 69168 KB | Output is correct |
19 | Correct | 56 ms | 70028 KB | Output is correct |
20 | Correct | 54 ms | 70080 KB | Output is correct |
21 | Correct | 40 ms | 64972 KB | Output is correct |
22 | Correct | 50 ms | 69328 KB | Output is correct |
23 | Correct | 56 ms | 68684 KB | Output is correct |
24 | Correct | 56 ms | 69740 KB | Output is correct |
25 | Correct | 52 ms | 69988 KB | Output is correct |
26 | Correct | 55 ms | 70036 KB | Output is correct |
27 | Correct | 53 ms | 70060 KB | Output is correct |
28 | Correct | 57 ms | 70136 KB | Output is correct |
29 | Correct | 65 ms | 69968 KB | Output is correct |
30 | Correct | 57 ms | 70092 KB | Output is correct |
31 | Correct | 65 ms | 70012 KB | Output is correct |
32 | Correct | 58 ms | 70040 KB | Output is correct |
33 | Correct | 77 ms | 70132 KB | Output is correct |
34 | Correct | 85 ms | 70108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 63720 KB | Output is correct |
2 | Correct | 32 ms | 63700 KB | Output is correct |
3 | Correct | 32 ms | 63632 KB | Output is correct |
4 | Correct | 33 ms | 63692 KB | Output is correct |
5 | Correct | 32 ms | 63652 KB | Output is correct |
6 | Correct | 37 ms | 63728 KB | Output is correct |
7 | Correct | 33 ms | 63628 KB | Output is correct |
8 | Correct | 36 ms | 63736 KB | Output is correct |
9 | Correct | 38 ms | 63824 KB | Output is correct |
10 | Correct | 36 ms | 64040 KB | Output is correct |
11 | Correct | 35 ms | 63992 KB | Output is correct |
12 | Correct | 41 ms | 63948 KB | Output is correct |
13 | Correct | 35 ms | 63940 KB | Output is correct |
14 | Correct | 37 ms | 64160 KB | Output is correct |
15 | Correct | 39 ms | 64104 KB | Output is correct |
16 | Correct | 36 ms | 64336 KB | Output is correct |
17 | Correct | 45 ms | 66104 KB | Output is correct |
18 | Correct | 51 ms | 69200 KB | Output is correct |
19 | Correct | 52 ms | 70036 KB | Output is correct |
20 | Correct | 55 ms | 70092 KB | Output is correct |
21 | Correct | 38 ms | 64980 KB | Output is correct |
22 | Correct | 50 ms | 69348 KB | Output is correct |
23 | Correct | 51 ms | 68812 KB | Output is correct |
24 | Correct | 55 ms | 69840 KB | Output is correct |
25 | Correct | 61 ms | 70064 KB | Output is correct |
26 | Correct | 70 ms | 69968 KB | Output is correct |
27 | Correct | 55 ms | 70060 KB | Output is correct |
28 | Correct | 58 ms | 70132 KB | Output is correct |
29 | Correct | 67 ms | 69964 KB | Output is correct |
30 | Correct | 60 ms | 69964 KB | Output is correct |
31 | Correct | 77 ms | 70004 KB | Output is correct |
32 | Correct | 57 ms | 69988 KB | Output is correct |
33 | Correct | 79 ms | 70144 KB | Output is correct |
34 | Correct | 78 ms | 70092 KB | Output is correct |
35 | Correct | 82 ms | 69352 KB | Output is correct |
36 | Correct | 50 ms | 67276 KB | Output is correct |
37 | Correct | 90 ms | 71244 KB | Output is correct |
38 | Correct | 89 ms | 71552 KB | Output is correct |
39 | Correct | 85 ms | 71592 KB | Output is correct |
40 | Correct | 89 ms | 71664 KB | Output is correct |
41 | Correct | 87 ms | 71536 KB | Output is correct |
42 | Correct | 55 ms | 70380 KB | Output is correct |
43 | Correct | 55 ms | 70416 KB | Output is correct |
44 | Correct | 55 ms | 70380 KB | Output is correct |
45 | Correct | 108 ms | 73556 KB | Output is correct |
46 | Correct | 100 ms | 73660 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 63684 KB | Output is correct |
2 | Correct | 32 ms | 63620 KB | Output is correct |
3 | Correct | 32 ms | 63688 KB | Output is correct |
4 | Correct | 32 ms | 63728 KB | Output is correct |
5 | Correct | 33 ms | 63700 KB | Output is correct |
6 | Correct | 34 ms | 63700 KB | Output is correct |
7 | Correct | 32 ms | 63708 KB | Output is correct |
8 | Correct | 37 ms | 63704 KB | Output is correct |
9 | Correct | 32 ms | 63768 KB | Output is correct |
10 | Correct | 33 ms | 64000 KB | Output is correct |
11 | Correct | 36 ms | 64008 KB | Output is correct |
12 | Correct | 35 ms | 64036 KB | Output is correct |
13 | Correct | 35 ms | 63976 KB | Output is correct |
14 | Correct | 36 ms | 64096 KB | Output is correct |
15 | Correct | 36 ms | 64100 KB | Output is correct |
16 | Correct | 37 ms | 64292 KB | Output is correct |
17 | Correct | 45 ms | 66184 KB | Output is correct |
18 | Correct | 50 ms | 69196 KB | Output is correct |
19 | Correct | 54 ms | 69964 KB | Output is correct |
20 | Correct | 54 ms | 70024 KB | Output is correct |
21 | Correct | 42 ms | 65084 KB | Output is correct |
22 | Correct | 55 ms | 69340 KB | Output is correct |
23 | Correct | 54 ms | 68776 KB | Output is correct |
24 | Correct | 54 ms | 69816 KB | Output is correct |
25 | Correct | 54 ms | 70052 KB | Output is correct |
26 | Correct | 53 ms | 70052 KB | Output is correct |
27 | Correct | 55 ms | 69992 KB | Output is correct |
28 | Correct | 61 ms | 70032 KB | Output is correct |
29 | Correct | 71 ms | 70068 KB | Output is correct |
30 | Correct | 58 ms | 69904 KB | Output is correct |
31 | Correct | 60 ms | 69992 KB | Output is correct |
32 | Correct | 59 ms | 70036 KB | Output is correct |
33 | Correct | 74 ms | 70136 KB | Output is correct |
34 | Correct | 89 ms | 70164 KB | Output is correct |
35 | Correct | 66 ms | 69408 KB | Output is correct |
36 | Correct | 44 ms | 67304 KB | Output is correct |
37 | Correct | 86 ms | 71240 KB | Output is correct |
38 | Correct | 86 ms | 71584 KB | Output is correct |
39 | Correct | 91 ms | 71648 KB | Output is correct |
40 | Correct | 87 ms | 71552 KB | Output is correct |
41 | Correct | 83 ms | 71604 KB | Output is correct |
42 | Correct | 56 ms | 70412 KB | Output is correct |
43 | Correct | 55 ms | 70380 KB | Output is correct |
44 | Correct | 58 ms | 70436 KB | Output is correct |
45 | Correct | 107 ms | 73652 KB | Output is correct |
46 | Correct | 104 ms | 73740 KB | Output is correct |
47 | Correct | 336 ms | 107288 KB | Output is correct |
48 | Correct | 269 ms | 138188 KB | Output is correct |
49 | Correct | 289 ms | 144828 KB | Output is correct |
50 | Correct | 343 ms | 152524 KB | Output is correct |
51 | Correct | 428 ms | 161088 KB | Output is correct |
52 | Correct | 440 ms | 161128 KB | Output is correct |
53 | Correct | 391 ms | 158964 KB | Output is correct |
54 | Correct | 323 ms | 157956 KB | Output is correct |
55 | Correct | 319 ms | 157888 KB | Output is correct |
56 | Correct | 348 ms | 158980 KB | Output is correct |
57 | Correct | 523 ms | 158036 KB | Output is correct |
58 | Correct | 332 ms | 158228 KB | Output is correct |
59 | Correct | 345 ms | 158420 KB | Output is correct |
60 | Correct | 396 ms | 158716 KB | Output is correct |
61 | Correct | 351 ms | 158492 KB | Output is correct |
62 | Correct | 416 ms | 160988 KB | Output is correct |
63 | Correct | 443 ms | 176760 KB | Output is correct |
64 | Correct | 459 ms | 182884 KB | Output is correct |
65 | Correct | 502 ms | 191688 KB | Output is correct |
66 | Execution timed out | 1084 ms | 191340 KB | Time limit exceeded |
67 | Halted | 0 ms | 0 KB | - |