Submission #1187147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187147		origabai	Sky Walking (IOI19_walk)	C++20	10 / 100	4119 ms	933796 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#include "walk.h"
typedef long long ll;
#pragma GCC optimize("Ofast")
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){
    int n = x.size();
    vector<ll> build_pts[n];
    for (int i=0;i<n;i++){
        build_pts[i].push_back(0);
    }
    unordered_map<ll,unordered_map<ll,vector<pair<ll,ll>>>> out; // (x,y) -> (x,y)
    for (int i=0;i<l.size();i++){
        vector<pair<ll,ll>> pts;
        for (int j=l[i];j<=r[i];j++){
            if (y[i] <= h[j]){
                pts.push_back({x[j],y[i]});
                build_pts[j].push_back(y[i]);
            }
        }
        for (int j=1;j<pts.size();j++){
            out[pts[j].first][pts[j].second].push_back(pts[j-1]);
            out[pts[j-1].first][pts[j-1].second].push_back(pts[j]);
        }
    }
    for (int i=0;i<n;i++){
        sort(build_pts[i].begin(),build_pts[i].end());
        for (int j=1;j<build_pts[i].size();j++){
            out[x[i]][build_pts[i][j-1]].push_back({x[i],build_pts[i][j]});
            out[x[i]][build_pts[i][j]].push_back({x[i],build_pts[i][j-1]});
        }
    }
    // unordered_map<pair<ll,ll>,bool> vis;
    // unordered_map<pair<ll,ll>,ll> dist;
    unordered_map<ll,unordered_map<ll,bool>> vis;
    unordered_map<ll,unordered_map<ll,ll>> dist;
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>>> prq;
    prq.push({0,{x[s],0}});
    while (prq.size()){
        auto [d, v] = prq.top();
        prq.pop();
        if (vis[v.first][v.second]) continue;
        vis[v.first][v.second] = 1;
        dist[v.first][v.second] = d;
        for (auto &u : out[v.first][v.second]){
            if (!vis[u.first][u.second]){
                prq.push({d + abs(u.first-v.first)+abs(u.second-v.second),u});
            }
        }
    }
    if (!vis[x[g]][0]){
        return -1;
    } else {
        return dist[x[g]][0];
    }
}

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