# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25509 | 2017-06-22T14:46:08 Z | gabrielsimoes | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 19 ms | 3120 KB |
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef long long ll; const int MAXN = 3e4+10; const ll INF = ll(MAXN)*ll(MAXN)*ll(MAXN); int N, M, X, Y; vector<int> v[MAXN]; bool ok[MAXN]; ll d[MAXN]; void dijkstra() { for (int i = 0; i < N; i++) d[i] = INF; d[X] = 0; while (true) { int cur = -1; for (int i = 0; i < N; i++) if (!ok[i] && (cur == -1 || d[i] < d[cur])) cur = i; if (cur == -1) return; ok[cur] = true; for (int dx : v[cur]) { int i = cur - dx, cnt = 1; while (i > 0) d[i] = min(d[i], d[cur] + (cur - i)/dx), i -= dx, cnt++; i = cur + dx, cnt = 1; while (i < N) d[i] = min(d[i], d[cur] + cnt), i += dx, cnt++; } } } int main() { scanf("%d %d", &N, &M); for (int i = 0,a,b; i < M; i++) { scanf("%d %d", &a, &b); if (i == 0) X = a; else if (i == 1) Y = a; if (b != 0) v[a].push_back(b); } for (int i = 0; i < N; i++) sort(v[i].begin(), v[i].end()), v[i].resize(unique(v[i].begin(), v[i].end()) - v[i].begin()); dijkstra(); printf("%lld\n", d[Y] < INF ? d[Y] : -1); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2988 KB | Output is correct |
2 | Correct | 0 ms | 2988 KB | Output is correct |
3 | Correct | 0 ms | 2988 KB | Output is correct |
4 | Correct | 0 ms | 2988 KB | Output is correct |
5 | Correct | 0 ms | 2988 KB | Output is correct |
6 | Correct | 0 ms | 2988 KB | Output is correct |
7 | Correct | 0 ms | 2988 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2988 KB | Output is correct |
2 | Correct | 0 ms | 2988 KB | Output is correct |
3 | Correct | 0 ms | 2988 KB | Output is correct |
4 | Correct | 0 ms | 2988 KB | Output is correct |
5 | Correct | 0 ms | 2988 KB | Output is correct |
6 | Correct | 0 ms | 2988 KB | Output is correct |
7 | Correct | 0 ms | 2988 KB | Output is correct |
8 | Correct | 0 ms | 2988 KB | Output is correct |
9 | Correct | 0 ms | 2988 KB | Output is correct |
10 | Correct | 0 ms | 2988 KB | Output is correct |
11 | Correct | 0 ms | 2988 KB | Output is correct |
12 | Correct | 0 ms | 2988 KB | Output is correct |
13 | Correct | 0 ms | 2988 KB | Output is correct |
14 | Correct | 0 ms | 2988 KB | Output is correct |
15 | Correct | 0 ms | 2988 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2988 KB | Output is correct |
2 | Correct | 0 ms | 2988 KB | Output is correct |
3 | Correct | 0 ms | 2988 KB | Output is correct |
4 | Correct | 0 ms | 2988 KB | Output is correct |
5 | Correct | 0 ms | 2988 KB | Output is correct |
6 | Correct | 0 ms | 2988 KB | Output is correct |
7 | Correct | 0 ms | 2988 KB | Output is correct |
8 | Correct | 0 ms | 2988 KB | Output is correct |
9 | Correct | 0 ms | 2988 KB | Output is correct |
10 | Correct | 0 ms | 2988 KB | Output is correct |
11 | Correct | 0 ms | 2988 KB | Output is correct |
12 | Correct | 0 ms | 2988 KB | Output is correct |
13 | Correct | 0 ms | 2988 KB | Output is correct |
14 | Correct | 0 ms | 2988 KB | Output is correct |
15 | Correct | 0 ms | 2988 KB | Output is correct |
16 | Correct | 0 ms | 2988 KB | Output is correct |
17 | Correct | 0 ms | 2988 KB | Output is correct |
18 | Correct | 6 ms | 2988 KB | Output is correct |
19 | Correct | 9 ms | 2988 KB | Output is correct |
20 | Correct | 19 ms | 3120 KB | Output is correct |
21 | Correct | 0 ms | 2988 KB | Output is correct |
22 | Correct | 6 ms | 2988 KB | Output is correct |
23 | Correct | 6 ms | 2988 KB | Output is correct |
24 | Correct | 9 ms | 2988 KB | Output is correct |
25 | Correct | 9 ms | 2988 KB | Output is correct |
26 | Correct | 9 ms | 2988 KB | Output is correct |
27 | Correct | 6 ms | 2988 KB | Output is correct |
28 | Incorrect | 9 ms | 3120 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2988 KB | Output is correct |
2 | Correct | 0 ms | 2988 KB | Output is correct |
3 | Correct | 0 ms | 2988 KB | Output is correct |
4 | Correct | 0 ms | 2988 KB | Output is correct |
5 | Correct | 0 ms | 2988 KB | Output is correct |
6 | Correct | 0 ms | 2988 KB | Output is correct |
7 | Correct | 0 ms | 2988 KB | Output is correct |
8 | Correct | 0 ms | 2988 KB | Output is correct |
9 | Correct | 0 ms | 2988 KB | Output is correct |
10 | Correct | 0 ms | 2988 KB | Output is correct |
11 | Correct | 0 ms | 2988 KB | Output is correct |
12 | Correct | 0 ms | 2988 KB | Output is correct |
13 | Correct | 0 ms | 2988 KB | Output is correct |
14 | Correct | 0 ms | 2988 KB | Output is correct |
15 | Correct | 0 ms | 2988 KB | Output is correct |
16 | Correct | 0 ms | 2988 KB | Output is correct |
17 | Correct | 0 ms | 2988 KB | Output is correct |
18 | Correct | 6 ms | 2988 KB | Output is correct |
19 | Correct | 9 ms | 2988 KB | Output is correct |
20 | Correct | 19 ms | 3120 KB | Output is correct |
21 | Correct | 0 ms | 2988 KB | Output is correct |
22 | Correct | 6 ms | 2988 KB | Output is correct |
23 | Correct | 6 ms | 2988 KB | Output is correct |
24 | Correct | 6 ms | 2988 KB | Output is correct |
25 | Correct | 9 ms | 2988 KB | Output is correct |
26 | Correct | 9 ms | 2988 KB | Output is correct |
27 | Correct | 9 ms | 2988 KB | Output is correct |
28 | Incorrect | 9 ms | 3120 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2988 KB | Output is correct |
2 | Correct | 0 ms | 2988 KB | Output is correct |
3 | Correct | 0 ms | 2988 KB | Output is correct |
4 | Correct | 0 ms | 2988 KB | Output is correct |
5 | Correct | 0 ms | 2988 KB | Output is correct |
6 | Correct | 0 ms | 2988 KB | Output is correct |
7 | Correct | 0 ms | 2988 KB | Output is correct |
8 | Correct | 0 ms | 2988 KB | Output is correct |
9 | Correct | 0 ms | 2988 KB | Output is correct |
10 | Correct | 0 ms | 2988 KB | Output is correct |
11 | Correct | 0 ms | 2988 KB | Output is correct |
12 | Correct | 0 ms | 2988 KB | Output is correct |
13 | Correct | 0 ms | 2988 KB | Output is correct |
14 | Correct | 0 ms | 2988 KB | Output is correct |
15 | Correct | 0 ms | 2988 KB | Output is correct |
16 | Correct | 0 ms | 2988 KB | Output is correct |
17 | Correct | 0 ms | 2988 KB | Output is correct |
18 | Correct | 6 ms | 2988 KB | Output is correct |
19 | Correct | 6 ms | 2988 KB | Output is correct |
20 | Correct | 19 ms | 3120 KB | Output is correct |
21 | Correct | 0 ms | 2988 KB | Output is correct |
22 | Correct | 6 ms | 2988 KB | Output is correct |
23 | Correct | 3 ms | 2988 KB | Output is correct |
24 | Correct | 9 ms | 2988 KB | Output is correct |
25 | Correct | 9 ms | 2988 KB | Output is correct |
26 | Correct | 9 ms | 2988 KB | Output is correct |
27 | Correct | 9 ms | 2988 KB | Output is correct |
28 | Incorrect | 9 ms | 3120 KB | Output isn't correct |
29 | Halted | 0 ms | 0 KB | - |