# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
745943 | 2023-05-21T09:51:02 Z | nguyentunglam | Railway Trip 2 (JOI22_ho_t4) | C++17 | 109 ms | 155616 KB |
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 5010; int trace[N], d[N], f[N][N]; bool adj[N][N]; int n, m, k; void bfs(int s) { for(int i = 1; i <= n; i++) trace[i] = d[i] = 0; queue<int> q; q.push(s); trace[s] = -1; d[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for(int v = 1; v <= n; v++) if (adj[u][v] && !trace[v]) { d[v] = d[u] + 1; trace[v] = u; q.push(v); } } for(int j = s + 2; j <= n; j++) if (d[j] < d[j - 1]) assert(0); for(int j = s - 2; j >= 1; j--) if (d[j] < d[j + 1]) assert(0); for(int j = 1; j <= n; j++) f[s][j] = d[j] - 1; } int main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen ("task.inp", "r")) { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); } if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } cin >> n >> k >> m; for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; if (a < b) for(int j = a; j <= min(a + k - 1, b - 1); j++) for(int k = j + 1; k <= b; k++) adj[j][k] = 1; else for(int j = a; j >= max(a - k + 1, b + 1); j--) for(int k = j - 1; k >= b; k--) adj[j][k] = 1; } for(int i = 1; i <= n; i++) bfs(i); int q; cin >> q; while (q--) { int s, t; cin >> s >> t; cout << f[s][t] << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 2516 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 2516 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 408 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 396 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 109 ms | 155616 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 2516 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |