제출 #1183718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183718		Turkhuu	Railway Trip (JOI17_railway_trip)	C++20	20 / 100	2095 ms	8196 KiB

railway_trip

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int N = 100002;
int a[N], dis[N];
vector<int> adj[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    FOR(i, 1, n) cin >> a[i];
    vector<int> stk;
    FOR(i, 1, n) {
        while (!stk.empty() && a[stk.back()] < a[i]) stk.pop_back();
        if (!stk.empty()) {
            int j = stk.back();
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
        stk.push_back(i);
    }
    stk.clear();
    ROF(i, n, 1) {
        while (!stk.empty() && a[stk.back()] < a[i]) stk.pop_back();
        if (!stk.empty()) {
            int j = stk.back();
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
        stk.push_back(i);
    }
    while (q--) {
        int s, t;
        cin >> s >> t;
        FOR(i, 1, n) dis[i] = -1;
        queue<int> q;
        for (dis[s] = 0, q.push(s); !q.empty(); q.pop()) {
            int x = q.front();
            for (int y : adj[x]) {
                if (dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    q.push(y);
                }
            }
        }
        cout << dis[t] - 1 << "\n";
    }
    return 6/22;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55