Submission #1077283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077283		isaachew	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2044 ms	17720 KiB

railway_trip

#include <bits/stdc++.h>
/*
 20p: just Dijkstra
 45p: keep left/right for each level (impossible to go past them)
 Cartesian tree-like
 
 Square root?
 
 
 */
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::vector<int> levels;
    int n,k,q;
    std::cin>>n>>k>>q;
    std::vector<std::vector<int>> edges(n);
    std::vector<std::vector<int>> bylevel(k);
    std::set<int> nums;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        x--;
        levels.push_back(x);
        bylevel[x].push_back(i);
    }
    for(int i=k;i--;){
        for(int j=0;j<bylevel[i].size();j++){
            nums.insert(bylevel[i][j]);
        }
        for(int j=0;j<bylevel[i].size();j++){
            if(bylevel[i][j]!=0)edges[bylevel[i][j]].push_back(*--nums.lower_bound(bylevel[i][j]));
            if(bylevel[i][j]!=n-1)edges[bylevel[i][j]].push_back(*nums.upper_bound(bylevel[i][j]));
            //std::cout<<edges[bylevel[i][j]][0]<<'\n';
        }
    }
    for(int i=0;i<q;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        
        std::vector<int> dists1(n,1e9),dists2(n,1e9);
        std::priority_queue<std::pair<int,int>> dijkstra;
        dijkstra.push({-0,a});
        while(!dijkstra.empty()){
            std::pair<int,int> cur=dijkstra.top();
            dijkstra.pop();
            if(dists1[cur.second]<=-cur.first)continue;
            dists1[cur.second]=-cur.first;
            for(int i:edges[cur.second]){
                dijkstra.push({cur.first-1,i});
            }
        }
        dijkstra.push({-0,b});
        while(!dijkstra.empty()){
            std::pair<int,int> cur=dijkstra.top();
            dijkstra.pop();
            if(dists2[cur.second]<=-cur.first)continue;
            dists2[cur.second]=-cur.first;
            for(int i:edges[cur.second]){
                dijkstra.push({cur.first-1,i});
            }
        }
        int mndst=1e9;
        for(int j=0;j<n;j++){
            //std::cout<<dists1[j]+dists2[j]<<'\n';
            mndst=std::min(mndst,dists1[j]+dists2[j]);
        }
        std::cout<<mndst-1<<'\n';
    }
}

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