Submission #21326

#	Time	Username	Problem	Language	Result	Execution time	Memory
21326		Ushio	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2000 ms	9140 KiB

railway_trip

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55