oj.uz

Submission #745897

# Submission time Handle Problem Language Result Execution time Memory
745897 2023-05-21T09:26:19 Z nguyentunglam Railway Trip 2 (JOI22_ho_t4) C++17
0 / 100
 33 ms 47176 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
0 / 8.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2516 KB Execution killed with signal 6
2 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 33 ms 47176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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