Submission #1079051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079051		veehj	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2069 ms	14652 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(x) (x).begin(), (x).end()

int main() {
    ll n, k, Q; cin >> n >> k >> Q;
    vector<vector<ll>> adj(n);
    vector<ll> l(n), a(Q), b(Q); for(auto& u : l) cin >> u;
    for(ll i=0; i<Q; i++) cin >> a[i] >> b[i];
    stack<ll> s;
    s.push(0);
    for(ll i=1; i<n; i++){
        while(!s.empty() && l[s.top()]<l[i]) s.pop();
        adj[i].pb(s.top());
        adj[s.top()].pb(i);
        s.push(i);
    }
    while(!s.empty()) s.pop();
    s.push(n-1);
    for(ll i=n-2; i>=0; i--){
        while(!s.empty() && l[s.top()]<l[i]) s.pop();
        adj[i].pb(s.top());
        adj[s.top()].pb(i);
        s.push(i);
    }
    for(ll i=0; i<Q; i++){
        a[i]--; b[i]--;
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
        q.push({0, a[i]});
        vector<ll> dist(n, -1);
        dist[a[i]]=0;
        while(!q.empty()){
            ll pl=q.top().S, curr=q.top().F;
            q.pop();
            if(dist[pl]<curr) continue;
            for(auto& u : adj[pl]){
                if(curr+1>=dist[u] && dist[u]!=-1) continue;
                dist[u]=curr+1;
                q.push({dist[u], u});
            }
        }
        cout << dist[b[i]]-1 << endl;
    }
}

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