Submission #1077294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077294		isaachew	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2067 ms	31944 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;
    if(k>20){
        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';
        }
    }else{
        std::vector<std::vector<int>> bylevel(k);
        //std::vector<std::map<int,int>> bylevel_set(k);
        std::vector<std::vector<int>> llevel(k,std::vector<int>(n)),rlevel(k,std::vector<int>(n)),linds(k,std::vector<int>(n));
        for(int i=0;i<n;i++){
            int x;
            std::cin>>x;
            x--;
            levels.push_back(x);
            for(int k=0;k<=x;k++)bylevel[k].push_back(i);
        }
        for(int i=0;i<k;i++){
            int p=0;
            for(int j=0;j<bylevel[i].size();j++){
                linds[i][bylevel[i][j]]=j;
                for(;p<=bylevel[i][j];p++){
                    rlevel[i][p]=bylevel[i][j];
                }
            }
            p=n-1;
            for(int j=bylevel[i].size();--j;){
                for(;p>=bylevel[i][j];p--){
                    llevel[i][p]=bylevel[i][j];
                }
            }
        }
        for(int i=0;i<q;i++){
            int a,b;
            std::cin>>a>>b;
            a--,b--;
            if(a>b)std::swap(a,b);
            int la=a,lda=0,ra=a,rda=0;
            int lb=b,ldb=0,rb=b,rdb=0;
            int res=1e9;
            for(int j=0;j<k;j++){
                if(levels[la]<j){
                    int nlev=llevel[j][la];
                    int curt=linds[j-1][la];
                    int nxtt=linds[j-1][nlev];
                    lda+=std::abs(curt-nxtt);
                    la=nlev;
                }
                if(levels[ra]<j){
                    int nlev=rlevel[j][ra];
                    int curt=linds[j-1][ra];
                    int nxtt=linds[j-1][nlev];
                    rda+=std::abs(curt-nxtt);
                    ra=nlev;
                }
                lda=std::min(rda+1,lda);rda=std::min(lda+1,rda);
                if(levels[lb]<j){
                    int nlev=llevel[j][lb];
                    int curt=linds[j-1][lb];
                    int nxtt=linds[j-1][nlev];
                    ldb+=std::abs(curt-nxtt);
                    lb=nlev;
                }
                if(levels[rb]<j){
                    int nlev=rlevel[j][rb];
                    int curt=linds[j-1][rb];
                    int nxtt=linds[j-1][nlev];
                    rdb+=std::abs(curt-nxtt);
                    rb=nlev;
                }
                ldb=std::min(rdb+1,ldb);rdb=std::min(ldb+1,rdb);
                res=std::min(res,ldb+rda+linds[j][lb]-linds[j][ra]);
            }
            std::cout<<res-1<<'\n';
        }
    }
}

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