Submission #1207521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207521		Aviansh	Sky Walking (IOI19_walk)	C++20	10 / 100	4091 ms	606676 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;
    for(int i = 0;i<m;i++){
        array<int,2>las={-1,-1};
        for(int j = l[i];j<=r[i];j++){
            if(h[j]<y[i])
                continue;
            //intersection found (x[j],y[i])
            if(las[0]!=-1)
                g[{x[j],y[i]}].push_back(las);
            las={x[j],y[i]};
            pts.insert({x[j],y[i]});
        }
        las={-1,-1};
        for(int j = r[i];j>=l[i];j--){
            if(h[j]<y[i])
                continue;
            //intersection found (x[j],y[i])
            if(las[0]!=-1)
                g[{x[j],y[i]}].push_back(las);
            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: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43