# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
838768 | 2023-08-27T17:35:27 Z | nonono | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 1 ms | 1108 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] || d > f[u][0]) 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 | Incorrect | 1 ms | 1108 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 1 ms | 1108 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 1 ms | 1108 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 1 ms | 1108 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |