Submission #1207529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207529		Aviansh	Sky Walking (IOI19_walk)	C++20	24 / 100	4065 ms	481156 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e) {
    int n = x.size();
    int m = y.size();
    map<array<int,2>,vector<array<int,2>>>g;
    set<array<int,2>>pts;
    vector<array<int,3>>tempe(m);
    for(int i = 0;i<m;i++){
        tempe[i]={y[i],l[i],r[i]};
    }
    sort(tempe.begin(),tempe.end());
    reverse(tempe.begin(),tempe.end());
    for(int i = 0;i<m;i++){
        l[i]=tempe[i][1];
        r[i]=tempe[i][2];
        y[i]=tempe[i][0];
    }
    array<int,2>xs[n];
    for(int i = 0;i<n;i++){
        xs[i][0]=h[i];
        xs[i][1]=i;
    }
    sort(xs,xs+n);
    reverse(xs,xs+n);
    set<int>val;
    int z = 0;
    for(int i = 0;i<m;i++){
        while(z<n&&xs[z][0]>=y[i]){
            val.insert(xs[z][1]);
            z++;
        }
        array<int,2>las={-1,-1};
        auto it = val.lower_bound(l[i]);
        while(it!=val.end()){
            int j = (*it);
            it++;
            if(j>r[i])
                break;
            if(las[0]!=-1){
                g[{x[j],y[i]}].push_back(las);
                g[las].push_back({x[j],y[i]});
            }
            las={x[j],y[i]};
            pts.insert({x[j],y[i]});
        }
    }
    array<int,2>las={-1,-1};
    pts.insert({x[s],0});
    pts.insert({x[e],0});
    for(array<int,2>a:pts){
        if(a[0]==las[0]){
            //same coordinate, must connect.
            g[a].push_back(las);
            g[las].push_back(a);
        }
        las=a;
    }
    priority_queue<pair<long long,array<int,2>>,vector<pair<long long,array<int,2>>>,greater<pair<long long,array<int,2>>>>pq;
    pq.push({0,{x[s],0}});
    map<array<int,2>,long long>dists;
    while(pq.size()){
        pair<long long,array<int,2>>p = pq.top();
        pq.pop();
        if(dists.find(p.second)!=dists.end()&&dists[p.second]<=p.first)
            continue;
        dists[p.second]=p.first;
        for(array<int,2>e:g[p.second]){
            pq.push({p.first+abs(e[0]-p.second[0])+abs(e[1]-p.second[1]),e});
        }
    }
    if(dists.find({x[e],0})==dists.end()){
        return -1;
    }
    return dists[{x[e],0}];
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43