Submission #736950

#	Time	Username	Problem	Language	Result	Execution time	Memory
736950		finn__	Sky Walking (IOI19_walk)	C++17	33 / 100	1150 ms	137724 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using L = long long;

vector<size_t> last_node;
vector<vector<pair<size_t, L>>> G;
vector<pair<L, L>> p;
vector<L> d;
vector<pair<size_t, bool>> events;

L min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r,
               vector<int> y, int s, int g)
{
    size_t const n = x.size(), m = l.size();
    last_node.resize(m);
    fill(last_node.begin(), last_node.end(), SIZE_MAX);
    for (size_t i = 0; i < m; ++i)
        events.emplace_back(i, 0), events.emplace_back(i, 1);
    sort(events.begin(), events.end(), [&](auto const &u, auto const &v)
         { int const a = u.second ? r[u.first] : l[u.first],
                     b = v.second ? r[v.first] : l[v.first];
           return a == b ? !u.second && v.second : a < b; });

    auto compare_segment_height = [&](size_t const &i, size_t const &j)
    { return y[i] < y[j]; };

    multiset<size_t, decltype(compare_segment_height)> segments(compare_segment_height);
    map<pair<L, L>, size_t> nodes;

    auto get_node = [&](L const &i, L const &j)
    {
        auto it = nodes.find({i, j});
        if (it != nodes.end())
            return it->second;
        nodes[{i, j}] = G.size();
        p.emplace_back(i, j);
        G.emplace_back();
        return G.size() - 1;
    };

    for (auto const &[i, b] : events)
    {
        size_t const curr_node = get_node(b ? x[r[i]] : x[l[i]], y[i]);
        if (last_node[i] != SIZE_MAX)
        {
            G[curr_node].emplace_back(last_node[i], p[curr_node].first - p[last_node[i]].first);
            G[last_node[i]].emplace_back(curr_node, p[curr_node].first - p[last_node[i]].first);
        }
        last_node[i] = curr_node;
        if (b)
            segments.erase(segments.find(i));
        auto it = segments.upper_bound(i);
        if (it != segments.end() && h[b ? r[i] : l[i]] >= y[*it])
        {
            size_t const neighbor = get_node(b ? x[r[i]] : x[l[i]], y[*it]);
            G[curr_node].emplace_back(neighbor, y[*it] - y[i]);
            G[neighbor].emplace_back(curr_node, y[*it] - y[i]);
            G[neighbor].emplace_back(last_node[*it], p[neighbor].first - p[last_node[*it]].first);
            G[last_node[*it]].emplace_back(neighbor, p[neighbor].first - p[last_node[*it]].first);
            last_node[*it] = neighbor;
        }
        it = segments.lower_bound(i);
        if (!segments.empty() && it != segments.begin() && y[*prev(it)] < y[i])
        {
            --it;
            size_t const neighbor = get_node(b ? x[r[i]] : x[l[i]], y[*it]);
            G[curr_node].emplace_back(neighbor, y[i] - y[*it]);
            G[neighbor].emplace_back(curr_node, y[i] - y[*it]);
            G[neighbor].emplace_back(last_node[*it], p[neighbor].first - p[last_node[*it]].first);
            G[last_node[*it]].emplace_back(neighbor, p[neighbor].first - p[last_node[*it]].first);
            last_node[*it] = neighbor;
        }
        if (!b)
            segments.insert(i);
    }

    priority_queue<pair<L, size_t>> q;
    d.resize(G.size());
    fill(d.begin(), d.end(), LLONG_MAX);
    for (size_t i = 0; i < G.size(); ++i)
        if (p[i].first == x[s])
            d[i] = p[i].second, q.emplace(-d[i], i);

    while (!q.empty())
    {
        auto const [f, u] = q.top();
        q.pop();
        if (-f != d[u])
            continue;
        for (auto const &[v, w] : G[u])
            if (-f + w < d[v])
            {
                d[v] = -f + w;
                q.emplace(-d[v], v);
            }
    }

    L min_distance = LLONG_MAX;
    for (size_t i = 0; i < G.size(); ++i)
        if (p[i].first == x[g] && d[i] != LLONG_MAX)
            min_distance = min(min_distance, d[i] + p[i].second);
    return min_distance == LLONG_MAX ? -1 : min_distance;
}

Compilation message (stderr)

walk.cpp: In function 'L min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:15:18: warning: unused variable 'n' [-Wunused-variable]
   15 |     size_t const n = x.size(), m = l.size();
      |                  ^

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