Submission #1063355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063355		Unforgettablepl	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2032 ms	95252 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

void main2(int n,int k){
    int q;
    cin >> q;
    vector<int> l(n+1);
    vector<vector<int>> idxes(k+1);
    for(int i=1;i<=n;i++)cin>>l[i];
    vector<vector<int>> adj(n+1);
    stack<pair<int,int>> s;
    for(int i=1;i<=n;i++) {
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    while(!s.empty())s.pop();
    for(int i=n;i;i--){
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    for(int i=1;i<=q;i++) {
        int a,b;
        cin >> a >> b;
        vector<bool> visited(n+1);
        queue<pair<int,int>> qu;
        qu.emplace(-1,a);
        while(!qu.empty()) {
            auto [dist,idx] = qu.front();qu.pop();
            if(visited[idx])continue;
            visited[idx]=true;
            if(idx==b) {
                cout << dist << '\n';
                break;
            }
            for(int&x:adj[idx])if(!visited[x])qu.emplace(dist+1,x);
        }
    }
    exit(0);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    if(k>20)main2(n,k);
    int q;
    cin >> q;
    vector<int> l(n+2);
    for(int i=1;i<=n;i++)cin>>l[i];
    l[0]=l[n+1]=k+1;
    vector pref(k+1,vector(n+1,0));
    for(int i=1;i<=k;i++) {
        for(int j=1;j<=n;j++) {
            pref[i][j]=pref[i][j-1];
            if(l[j]>=i)pref[i][j]++;
        }
    }
    vector nearest_left(k+1,vector<pair<int,int>>(n+1,{INF,0}));
    vector nearest_right(k+1,vector<pair<int,int>>(n+1,{INF,0}));
    vector<vector<int>> adj(n+1);
    stack<pair<int,int>> s;
    for(int i=1;i<=n;i++) {
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    while(!s.empty())s.pop();
    for(int i=n;i;i--){
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    for(int i=1;i<=k;i++){
        {
            // nearest right calculation
            vector<bool> visited(n+1);
            priority_queue<tuple<int,int,int>> qu;
            for(int x=1;x<=n;x++)if(l[x]>=i)qu.emplace(0,x,x);
            while(!qu.empty()) {
                auto [dist,source,idx] = qu.top();qu.pop();dist=-dist;
                if(visited[idx])continue;
                visited[idx]=true;
                nearest_right[i][idx]={dist,source};
                for(int&x:adj[idx])if(!visited[x])qu.emplace(-dist-1,source,x);
            }
        }
        {
            // nearest left calculation
            vector<bool> visited(n+1);
            priority_queue<tuple<int,int,int>> qu;
            for(int x=1;x<=n;x++)if(l[x]>=i)qu.emplace(0,-x,x);
            while(!qu.empty()) {
                auto [dist,source,idx] = qu.top();qu.pop();dist=-dist;source=-source;
                if(visited[idx])continue;
                visited[idx]=true;
                nearest_left[i][idx]={dist,source};
                for(int&x:adj[idx])if(!visited[x])qu.emplace(-dist-1,-source,x);
            }
        }
    }
    for(int i=1;i<=q;i++) {
        int oa,ob;
        cin >> oa >> ob;
        if(ob<oa)swap(oa,ob);
        int ans = INF;
        for(int level=1;level<=k;level++) {
            if(nearest_left[level][ob].second<nearest_right[level][oa].second)break;
            int a = nearest_right[level][oa].second;
            int b = nearest_left[level][ob].second;
            int currdist = nearest_right[level][oa].first+nearest_left[level][ob].first;
            ans = min(ans,currdist+pref[level][b]-pref[level][a]-1);
        }
        cout << ans << '\n';
    }
}

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