oj.uz

Submission #21326

# Submission time Handle Problem Language Result Execution time Memory
21326 2017-04-13T08:29:12 Z Ushio Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 9140 KB 
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k, q;
    cin >> n >> k >> q;

    vector<int> A(n);
    vector<int> stk;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        int prev = -1;
        while (!stk.empty() && A[i] > A[stk.back()]) {
            if (A[stk.back()] > prev) {
                graph[i].push_back(stk.back());
                graph[stk.back()].push_back(i);
            }
            prev = A[stk.back()];
            stk.pop_back();
        }
        if (!stk.empty()) {
            graph[i].push_back(stk.back());
            graph[stk.back()].push_back(i);
        }
        stk.push_back(i);
    }
    while (q-- > 0) {
        int s, d;
        cin >> s >> d;
        s--; d--;
        vector<int> dist(n, -1);
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty() && dist[d] == -1) {
            int node = q.front();
            q.pop();
            for (int to: graph[node]) {
                if (dist[to] == -1) {
                    dist[to] = dist[node] + 1;
                    q.push(to);
                }
            }
        }
        cout << dist[d] - 1 << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2184 KB Output is correct
2 Correct 0 ms 2184 KB Output is correct
3 Correct 0 ms 2184 KB Output is correct
4 Correct 0 ms 2184 KB Output is correct
5 Correct 0 ms 2184 KB Output is correct
6 Correct 0 ms 2184 KB Output is correct
7 Correct 0 ms 2184 KB Output is correct
8 Correct 0 ms 2184 KB Output is correct
9 Correct 0 ms 2184 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2184 KB Output is correct
2 Correct 116 ms 8896 KB Output is correct
3 Correct 123 ms 8972 KB Output is correct
4 Correct 139 ms 9044 KB Output is correct
5 Correct 126 ms 9076 KB Output is correct
6 Correct 129 ms 9120 KB Output is correct
7 Correct 129 ms 9140 KB Output is correct
8 Correct 43 ms 8984 KB Output is correct
9 Correct 43 ms 8728 KB Output is correct
10 Correct 43 ms 8984 KB Output is correct
11 Correct 113 ms 8880 KB Output is correct
12 Correct 109 ms 8884 KB Output is correct
13 Correct 113 ms 8884 KB Output is correct
14 Correct 109 ms 8880 KB Output is correct
15 Correct 119 ms 8884 KB Output is correct
16 Correct 116 ms 8884 KB Output is correct
17 Correct 139 ms 9140 KB Output is correct
18 Correct 123 ms 9140 KB Output is correct
19 Correct 76 ms 9140 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 8920 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 9140 KB Execution timed out
2 Halted 0 ms 0 KB -