oj.uz

Submission #745948

# Submission time Handle Problem Language Result Execution time Memory
745948 2023-05-21T09:52:57 Z nguyentunglam Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 2000 ms 155520 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] && d[j] > 0 && d[j - 1] > 0) assert(0);
    for(int j = s - 2; j >= 1; j--) if (d[j] < d[j + 1] && d[j] > 0 && d[j + 1] > 0) 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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2864 KB Output is correct
2 Correct 54 ms 2884 KB Output is correct
3 Correct 74 ms 3020 KB Output is correct
4 Correct 40 ms 3020 KB Output is correct
5 Correct 77 ms 3020 KB Output is correct
6 Correct 82 ms 3144 KB Output is correct
7 Correct 72 ms 3016 KB Output is correct
8 Correct 80 ms 3092 KB Output is correct
9 Correct 78 ms 3168 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 52 ms 2628 KB Output is correct
12 Correct 32 ms 3044 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2864 KB Output is correct
2 Correct 54 ms 2884 KB Output is correct
3 Correct 74 ms 3020 KB Output is correct
4 Correct 40 ms 3020 KB Output is correct
5 Correct 77 ms 3020 KB Output is correct
6 Correct 82 ms 3144 KB Output is correct
7 Correct 72 ms 3016 KB Output is correct
8 Correct 80 ms 3092 KB Output is correct
9 Correct 78 ms 3168 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 52 ms 2628 KB Output is correct
12 Correct 32 ms 3044 KB Output is correct
13 Execution timed out 2085 ms 10188 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 412 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 3 ms 468 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 100 ms 155520 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 2864 KB Output is correct
2 Correct 54 ms 2884 KB Output is correct
3 Correct 74 ms 3020 KB Output is correct
4 Correct 40 ms 3020 KB Output is correct
5 Correct 77 ms 3020 KB Output is correct
6 Correct 82 ms 3144 KB Output is correct
7 Correct 72 ms 3016 KB Output is correct
8 Correct 80 ms 3092 KB Output is correct
9 Correct 78 ms 3168 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 52 ms 2628 KB Output is correct
12 Correct 32 ms 3044 KB Output is correct
13 Execution timed out 2085 ms 10188 KB Time limit exceeded
14 Halted 0 ms 0 KB -