oj.uz

Submission #800966

# Submission time Handle Problem Language Result Execution time Memory
800966 2023-08-02T03:05:44 Z resting Sky Walking (IOI19_walk) C++17
0 / 100
 1691 ms 91776 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 <= s && 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); b.clear();
    }
    {
        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 >= s) {
                    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);
    }
    {
        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 <= g && 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);
    }
    {
        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 >= g) {
                    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());
    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) {
        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();
        //cout << t.second.first << "," << t.second.second << endl;
        q.erase(q.begin());
        if (dst[t.second]) continue;
        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;
        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 },
//         0, 6) << 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 },
//         0, 6) << endl;
// }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 19700 KB Output is correct
2 Correct 1339 ms 78308 KB Output is correct
3 Correct 1226 ms 79868 KB Output is correct
4 Correct 1556 ms 83484 KB Output is correct
5 Correct 1673 ms 85464 KB Output is correct
6 Correct 1691 ms 87932 KB Output is correct
7 Correct 521 ms 44316 KB Output is correct
8 Correct 616 ms 74164 KB Output is correct
9 Correct 1575 ms 91776 KB Output is correct
10 Correct 543 ms 71236 KB Output is correct
11 Runtime error 11 ms 2772 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 19700 KB Output is correct
2 Correct 1339 ms 78308 KB Output is correct
3 Correct 1226 ms 79868 KB Output is correct
4 Correct 1556 ms 83484 KB Output is correct
5 Correct 1673 ms 85464 KB Output is correct
6 Correct 1691 ms 87932 KB Output is correct
7 Correct 521 ms 44316 KB Output is correct
8 Correct 616 ms 74164 KB Output is correct
9 Correct 1575 ms 91776 KB Output is correct
10 Correct 543 ms 71236 KB Output is correct
11 Runtime error 11 ms 2772 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -