oj.uz

Submission #780303

# Submission time Handle Problem Language Result Execution time Memory
780303 2023-07-12T08:04:50 Z 이성호(#10006) Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 9640 KB 
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int A[100005];
vector<int> adj[100005];
int dis[100005];

int get_dis(int s, int e)
{
    queue<int> q;
    fill(dis, dis + 100005, -1);
    dis[s] = 0; q.push(s);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i:adj[cur]) {
            if (dis[i] == -1) {
                dis[i] = dis[cur] + 1;
                q.push(i);
            }
        }
    }
    return dis[e];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, K, Q; cin >> N >> K >> Q;
    stack<int> st;
    for (int i = 1; i <= N; i++) cin >> A[i];
    vector<pair<int, int>> edge;
    for (int i = 1; i <= N; i++) {
        bool ok = true;
        while (!st.empty() && A[st.top()] <= A[i]) {
            edge.push_back(make_pair(st.top(), i));
            ok &= A[st.top()] != A[i];
            st.pop();
        }
        if (!st.empty() && ok) edge.push_back(make_pair(st.top(), i));
        st.push(i);
    }
    for (auto i:edge) {
        adj[i.first].push_back(i.second);
        adj[i.second].push_back(i.first);
    }
    while (Q--) {
        int a, b; cin >> a >> b;
        cout << get_dis(a, b) - 1 << '\n';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 130 ms 8468 KB Output is correct
3 Correct 167 ms 8676 KB Output is correct
4 Correct 171 ms 8868 KB Output is correct
5 Correct 247 ms 8928 KB Output is correct
6 Correct 134 ms 9128 KB Output is correct
7 Correct 164 ms 9436 KB Output is correct
8 Correct 35 ms 7504 KB Output is correct
9 Correct 41 ms 8124 KB Output is correct
10 Correct 36 ms 7868 KB Output is correct
11 Correct 113 ms 8344 KB Output is correct
12 Correct 115 ms 8396 KB Output is correct
13 Correct 111 ms 8276 KB Output is correct
14 Correct 111 ms 8396 KB Output is correct
15 Correct 109 ms 8424 KB Output is correct
16 Correct 108 ms 8364 KB Output is correct
17 Correct 282 ms 9504 KB Output is correct
18 Correct 143 ms 9444 KB Output is correct
19 Correct 81 ms 9416 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 8888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 9640 KB Time limit exceeded
2 Halted 0 ms 0 KB -