oj.uz

Submission #745895

# Submission time Handle Problem Language Result Execution time Memory
745895 2023-05-21T09:25:54 Z nguyentunglam Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 2000 ms 47232 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];
bool adj[N][N];
int n, m, k;
int bfs(int s, int t) {
    for(int i = 1; i <= n; i++) trace[i] = 0;
    queue<int> q;
    q.push(s); trace[s] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for(int v = 1; v <= n; v++) if (adj[u][v] && !trace[v]) {
            trace[v] = u;
            q.push(v);
        }
    }

    if (trace[t] == 0) return -1;
    vector<int> lst;
    while (t != s) {
        lst.push_back(t);
        t = trace[t];
    }
    reverse(lst.begin(), lst.end());
    int type = 0, pre = s, prepre = s, rev = 0;
    for(int j : lst) {
        if (prepre < pre && j < pre) rev++;
        if (prepre > pre && j > pre) rev++;
        prepre = pre;
        pre = j;
    }
//    if (rev > 1) assert(0);
    return lst.size();
}
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;
    }
    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >> t;
        cout << bfs(s, t) << endl;
    }
}

Compilation message

Main.cpp: In function 'int bfs(int, int)':
Main.cpp:30:9: warning: unused variable 'type' [-Wunused-variable]
   30 |     int type = 0, pre = s, prepre = s, rev = 0;
      |         ^~~~
Main.cpp: In function 'int main()':
Main.cpp:44:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:49:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1236 KB Output is correct
2 Correct 71 ms 1384 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 40 ms 1492 KB Output is correct
5 Correct 74 ms 1520 KB Output is correct
6 Correct 79 ms 1620 KB Output is correct
7 Correct 74 ms 1492 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 78 ms 1620 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 70 ms 1108 KB Output is correct
12 Correct 12 ms 1484 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1236 KB Output is correct
2 Correct 71 ms 1384 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 40 ms 1492 KB Output is correct
5 Correct 74 ms 1520 KB Output is correct
6 Correct 79 ms 1620 KB Output is correct
7 Correct 74 ms 1492 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 78 ms 1620 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 70 ms 1108 KB Output is correct
12 Correct 12 ms 1484 KB Output is correct
13 Execution timed out 2069 ms 8004 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 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 1 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 39 ms 47232 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 71 ms 1236 KB Output is correct
2 Correct 71 ms 1384 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 40 ms 1492 KB Output is correct
5 Correct 74 ms 1520 KB Output is correct
6 Correct 79 ms 1620 KB Output is correct
7 Correct 74 ms 1492 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 78 ms 1620 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 70 ms 1108 KB Output is correct
12 Correct 12 ms 1484 KB Output is correct
13 Execution timed out 2069 ms 8004 KB Time limit exceeded
14 Halted 0 ms 0 KB -