oj.uz

Submission #1077294

# Submission time Handle Problem Language Result Execution time Memory
1077294 2024-08-27T04:57:52 Z isaachew Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 31944 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 22 ms 16340 KB Output is correct
3 Correct 34 ms 30420 KB Output is correct
4 Correct 66 ms 12692 KB Output is correct
5 Correct 71 ms 12740 KB Output is correct
6 Correct 73 ms 12732 KB Output is correct
7 Correct 83 ms 16696 KB Output is correct
8 Correct 371 ms 14708 KB Output is correct
9 Correct 236 ms 16012 KB Output is correct
10 Correct 289 ms 13456 KB Output is correct
11 Correct 256 ms 15908 KB Output is correct
12 Correct 249 ms 14416 KB Output is correct
13 Correct 292 ms 13612 KB Output is correct
14 Correct 312 ms 15944 KB Output is correct
15 Correct 274 ms 14256 KB Output is correct
16 Correct 249 ms 13640 KB Output is correct
17 Correct 54 ms 15436 KB Output is correct
18 Correct 51 ms 15252 KB Output is correct
19 Correct 62 ms 17720 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 23236 KB Output is correct
2 Correct 61 ms 17728 KB Output is correct
3 Correct 73 ms 25116 KB Output is correct
4 Correct 76 ms 26432 KB Output is correct
5 Correct 95 ms 27708 KB Output is correct
6 Correct 85 ms 30412 KB Output is correct
7 Correct 98 ms 31944 KB Output is correct
8 Correct 27 ms 6348 KB Output is correct
9 Correct 38 ms 21196 KB Output is correct
10 Correct 57 ms 27336 KB Output is correct
11 Correct 49 ms 27336 KB Output is correct
12 Correct 49 ms 27336 KB Output is correct
13 Correct 46 ms 27348 KB Output is correct
14 Correct 51 ms 26824 KB Output is correct
15 Correct 86 ms 27080 KB Output is correct
16 Correct 93 ms 28844 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 17020 KB Time limit exceeded
2 Halted 0 ms 0 KB -