# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
838775 | 2023-08-27T17:47:47 Z | nonono | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 14 ms | 9300 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 i = 1; u + i * p < n; i ++) { int right = u + i * p; if(f[right][0] > d + i) { f[right][0] = d + i; pq.push({d + i, right, 0}); } } for(int i = 1; u - i * p >= 0; i --) { int left = u - i * p; if(f[left][0] > d + i) { f[left][0] = d + i; pq.push({d + i, left, 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 | 928 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 | 944 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 | Runtime error | 14 ms | 9196 KB | Execution killed with signal 11 |
10 | 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 | Runtime error | 12 ms | 9300 KB | Execution killed with signal 11 |
10 | 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 | Runtime error | 12 ms | 9300 KB | Execution killed with signal 11 |
10 | 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 | Runtime error | 11 ms | 9188 KB | Execution killed with signal 11 |
10 | Halted | 0 ms | 0 KB | - |