Submission #801498

#	Time	Username	Problem	Language	Result	Execution time	Memory
801498		resting	Sky Walking (IOI19_walk)	C++17	100 / 100	3081 ms	144520 KiB

walk

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

#define ll long long

const int inf = 1e9;

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(), m = l.size();
    vector<pair<int, pair<int, int>>> a, b, c;
    for (int i = 0; i < m; i++) a.push_back({ y[i], {l[i], r[i]} });
    sort(a.begin(), a.end());
    vector<pair<int, int>> bld;
    for (int i = 0; i < n; i++) bld.push_back({ h[i], i });
    bld.push_back({ 0, -1 }); // just for the sake of it
    sort(bld.begin(), bld.end());
    {
        int rght = inf;
        for (int i = n - 1; i >= 0; i--) {
            while (a.size() && a.back().first > bld[i].first) {
                if (rght != inf && a.back().second.first < rght && a.back().second.second > rght) {
                    b.push_back({ a.back().first, {a.back().second.first, rght } });
                    b.push_back({ a.back().first, {rght, a.back().second.second } });
                }
                else b.push_back(a.back());
                a.pop_back();
            }
            if (bld[i].second >= s)
                rght = min(rght, bld[i].second);
        }
        swap(a, b); reverse(a.begin(), a.end());
    }
    {
        int lft = -inf;
        for (int i = n - 1; i >= 0; i--) {
            while (a.size() && a.back().first > bld[i].first) {
                if (lft != -inf && a.back().second.first < lft && a.back().second.second > lft) {
                    b.push_back({ a.back().first, {a.back().second.first, lft } });
                    b.push_back({ a.back().first, {lft, a.back().second.second } });
                }
                else b.push_back(a.back());
                a.pop_back();
            }
            if (bld[i].second <= s)
                lft = max(lft, bld[i].second);
        }
        swap(a, b); reverse(a.begin(), a.end());
    }
    {
        int rght = inf;
        for (int i = n - 1; i >= 0; i--) {
            while (a.size() && a.back().first > bld[i].first) {
                if (rght != inf && a.back().second.first < rght && a.back().second.second > rght) {
                    b.push_back({ a.back().first, {a.back().second.first, rght } });
                    b.push_back({ a.back().first, {rght, a.back().second.second } });
                }
                else b.push_back(a.back());
                a.pop_back();
            }
            if (bld[i].second >= g)
                rght = min(rght, bld[i].second);
        }
        swap(a, b); reverse(a.begin(), a.end());
    }
    {
        int lft = -inf;
        for (int i = n - 1; i >= 0; i--) {
            while (a.size() && a.back().first > bld[i].first) {
                if (lft != -inf && a.back().second.first < lft && a.back().second.second > lft) {
                    b.push_back({ a.back().first, {a.back().second.first, lft } });
                    b.push_back({ a.back().first, {lft, a.back().second.second } });
                }
                else b.push_back(a.back());
                a.pop_back();
            }
            if (bld[i].second <= g)
                lft = max(lft, bld[i].second);
        }
        swap(a, b); reverse(a.begin(), a.end());
    }
    reverse(a.begin(), a.end());
    set<pair<int, int>> pts; // set of points
    map<pair<int, int>, vector<pair<int, int>>> adj;
    auto edge = [&](pair<int, int> a, pair<int, int> b) {
        adj[a].push_back(b); adj[b].push_back(a);
    };
    auto dist = [&](pair<int, int> a, pair<int, int> b) -> ll {
        return (ll)(abs(x[a.first] - x[b.first]) + abs(a.second - b.second));
    };
    for (auto& x : a) {

        //cout << x.first << "," << x.second.first << "," << x.second.second << endl;
        int prev = x.second.first;
        auto pt = pts.lower_bound({ x.second.first, 0 });
        while (pt != pts.end() && pt->first <= x.second.second) {
            edge({ pt->first, x.first }, { prev, x.first });
            edge({ pt->first, x.first }, { pt->first, pt->second });
            prev = pt->first;
            pts.erase(pt++);
        }
        edge({ x.second.second, x.first }, { prev, x.first });
        pts.insert({ x.second.first, x.first });
        pts.insert({ x.second.second, x.first });
    }
    for (auto& x : pts) {
        edge({ x.first, x.second }, { x.first, 0 });
    }

    map<pair<int, int>, ll> dst;
    set<pair<ll, pair<int, int>>> q;
    q.insert({ 1, {s, 0} });
    while (!q.empty()) {
        auto t = *q.begin();
        q.erase(q.begin());
        if (dst[t.second]) continue;
        // cout << t.first << "," << t.second.first << "," << t.second.second << endl;
        dst[t.second] = t.first;
        for (auto& x : adj[t.second]) {
            //cout << "bruh" << endl;
            q.insert({ dist(t.second, x) + t.first,  x });
        }
    }

    //construct & run dijkstra
    return dst[{g, 0}] - 1;
}

long long min_distance_stress(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {  // basically dijkstra
    int n = x.size(), m = l.size();
    map<pair<int, int>, ll> dist;
    set<pair<ll, pair<int, int>>> ss;
    ss.insert({ 1, {s, 0} });
    while (ss.size()) {
        auto t = *ss.begin();
        ss.erase(ss.begin());
        int tim = t.first, xx = t.second.first, yy = t.second.second;
        if (dist[t.second]) continue;
        //cout << xx << "," << yy << "," << tim << endl;
        dist[t.second] = t.first;
        for (int i = 0; i < m; i++) {
            for (int x2 = 0; x2 < n; x2++) {
                if (y[i] == yy && l[i] <= x2 && r[i] >= x2 && l[i] <= xx && r[i] >= xx && h[x2] >= y[i]) ss.insert({ tim + abs(x[x2] - x[xx]), {x2, yy} });
            }
            if (l[i] <= xx && r[i] >= xx && h[xx] >= y[i]) ss.insert({ tim + abs(y[i] - yy), {xx, y[i]} });
            ss.insert({ tim + yy, {xx, 0} });
        }
    }
    return dist[{g, 0}] - 1;
}

// int main() {
//     cout << min_distance_stress({ 0, 3, 5, 7, 10, 12, 14 },
//         { 8, 7, 9, 7, 6, 6, 9 },
//         { 0, 0, 0, 2, 2, 3, 4 },
//         { 1, 2, 6, 3, 6, 4, 6 },
//         { 1, 6, 8, 1, 7, 2, 5 },
//         1, 5) << endl; 
//     cout << min_distance({ 0, 3, 5, 7, 10, 12, 14 },
//         { 8, 7, 9, 7, 6, 6, 9 },
//         { 0, 0, 0, 2, 2, 3, 4 },
//         { 1, 2, 6, 3, 6, 4, 6 },
//         { 1, 6, 8, 1, 7, 2, 5 },
//         1, 5) << endl;
// }

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