oj.uz

Submission #745939

# Submission time Handle Problem Language Result Execution time Memory
745939 2023-05-21T09:49:08 Z nguyentunglam Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 2000 ms 155620 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 = 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

Main.cpp: In function 'int main()':
Main.cpp:29:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:30:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:34:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2844 KB Output is correct
2 Correct 62 ms 2876 KB Output is correct
3 Correct 76 ms 3024 KB Output is correct
4 Correct 43 ms 3052 KB Output is correct
5 Correct 131 ms 3068 KB Output is correct
6 Correct 84 ms 3136 KB Output is correct
7 Correct 74 ms 3028 KB Output is correct
8 Correct 93 ms 3144 KB Output is correct
9 Correct 90 ms 3128 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 51 ms 2632 KB Output is correct
12 Correct 33 ms 3028 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2844 KB Output is correct
2 Correct 62 ms 2876 KB Output is correct
3 Correct 76 ms 3024 KB Output is correct
4 Correct 43 ms 3052 KB Output is correct
5 Correct 131 ms 3068 KB Output is correct
6 Correct 84 ms 3136 KB Output is correct
7 Correct 74 ms 3028 KB Output is correct
8 Correct 93 ms 3144 KB Output is correct
9 Correct 90 ms 3128 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 51 ms 2632 KB Output is correct
12 Correct 33 ms 3028 KB Output is correct
13 Execution timed out 2067 ms 9868 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 155620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2844 KB Output is correct
2 Correct 62 ms 2876 KB Output is correct
3 Correct 76 ms 3024 KB Output is correct
4 Correct 43 ms 3052 KB Output is correct
5 Correct 131 ms 3068 KB Output is correct
6 Correct 84 ms 3136 KB Output is correct
7 Correct 74 ms 3028 KB Output is correct
8 Correct 93 ms 3144 KB Output is correct
9 Correct 90 ms 3128 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 51 ms 2632 KB Output is correct
12 Correct 33 ms 3028 KB Output is correct
13 Execution timed out 2067 ms 9868 KB Time limit exceeded
14 Halted 0 ms 0 KB -