Submission #801449

# Submission time Handle Problem Language Result Execution time Memory
801449 2023-08-02T06:10:15 Z resting Sky Walking (IOI19_walk) C++17
0 / 100
1837 ms 84648 KB
#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 < m; 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 (lft != -inf && a.size() && a.back().first > bld[i].first) {
    //             if (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;
// }
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 128 ms 19716 KB Output is correct
2 Correct 1429 ms 77508 KB Output is correct
3 Correct 1311 ms 79712 KB Output is correct
4 Correct 1717 ms 81148 KB Output is correct
5 Correct 1837 ms 84648 KB Output is correct
6 Correct 1791 ms 78552 KB Output is correct
7 Correct 590 ms 43084 KB Output is correct
8 Correct 643 ms 71760 KB Output is correct
9 Correct 1494 ms 75536 KB Output is correct
10 Correct 443 ms 62324 KB Output is correct
11 Runtime error 11 ms 2728 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 128 ms 19716 KB Output is correct
2 Correct 1429 ms 77508 KB Output is correct
3 Correct 1311 ms 79712 KB Output is correct
4 Correct 1717 ms 81148 KB Output is correct
5 Correct 1837 ms 84648 KB Output is correct
6 Correct 1791 ms 78552 KB Output is correct
7 Correct 590 ms 43084 KB Output is correct
8 Correct 643 ms 71760 KB Output is correct
9 Correct 1494 ms 75536 KB Output is correct
10 Correct 443 ms 62324 KB Output is correct
11 Runtime error 11 ms 2728 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -