Submission #1211364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211364		VMaksimoski008	Railway Trip (JOI17_railway_trip)	C++20	20 / 100	2094 ms	8100 KiB

railway_trip

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 5;

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, k, q; cin >> n >> k >> q;
    vector<int> a(n+1), g[n+1];
    for(int i=1; i<=n; i++) cin >> a[i];

    stack<int> st;
    for(int i=1; i<=n; i++) {
        while(!st.empty() && a[st.top()] < a[i]) st.pop();
        if(!st.empty()) {
            g[i].push_back( st.top() );
            g[st.top()].push_back(i);
        }
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i=n; i>=1; i--) {
        while(!st.empty() && a[st.top()] < a[i]) st.pop();
        if(!st.empty()) {
            g[i].push_back( st.top() );
            g[st.top()].push_back(i);
        }
        st.push(i);
    }

    while(q--) {
        int s, t, ans = 1e9; cin >> s >> t;
        vector<int> dist(n+1, 1e9); dist[s] = 0;
        queue<int> Q; Q.push(s);

        while(!Q.empty()) {
            int u = Q.front(); Q.pop();
            for(int v : g[u]) {
                if(dist[v] != 1e9) continue;
                dist[v] = dist[u] + 1;
                Q.push(v);
            }
        }

        ans = dist[t] - 1;
        for(int v : g[t]) ans = min(ans, dist[v]);
        cout << ans << '\n';
    }
}

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