oj.uz

Submission #977936

# Submission time Handle Problem Language Result Execution time Memory
977936 2024-05-08T14:09:50 Z opPO Sky Walking (IOI19_walk) C++14
0 / 100
 2374 ms 683312 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) (int)x.size()

using pii = pair<int, int>;

const int N = 2e6 + 52;
const int OO = 1e18;
vector<pii> g[N];
vector<int> hs[N];
map<pii, int> mapka;
int unused;

int get_id(int i, int h) {
    if (mapka.find(make_pair(i, h)) == mapka.end()) {
        hs[i].push_back(h);
        mapka[{i, h}] = unused++;
    }
    return mapka[{i, h}];
}

long long min_distance(std::vector<int32_t> x, std::vector<int32_t> h, std::vector<int32_t> l, std::vector<int32_t> r, std::vector<int32_t> y, int32_t S, int32_t F) {
    int n = sz(x);
    int m = sz(l);

    for (int i = 0; i < n; i++) {
        mapka[{i, 0}] = unused++;
        hs[i].push_back(0);
    }

    vector<pii> heights;
    for (int i = 0; i < n; i++) {
        heights.push_back({h[i], i});
    }
    sort(heights.rbegin(), heights.rend());
    vector<pair<int, pii>> skys;
    for (int i = 0; i < m; i++) {
        skys.push_back({y[i], {l[i], r[i]}});
    }
    sort(skys.rbegin(), skys.rend());

    set<int> can;
    int ptr = 0;
    for (int i = 0; i < m; i++) {
        int Y = skys[i].first;
        int L = skys[i].second.first, R = skys[i].second.second;
        while (ptr < n && heights[ptr].first >= Y) {
            can.insert(heights[ptr].second);
            ptr++;
        }

        auto it = can.lower_bound(L);
        vector<int> ps;
        while (it != can.end() && (*it) <= R) {
            ps.push_back(*it);
            ++it;
        }
        assert(sz(ps) >= 2);

        for (int i = 1; i < sz(ps); i++) {
            int prv = get_id(ps[i - 1], Y), cur = get_id(ps[i], Y);
            g[prv].push_back({cur, x[ps[i]] - x[ps[i - 1]]});
            g[cur].push_back({prv, x[ps[i]] - x[ps[i - 1]]});
        }
    }

    for (int i = 0; i < n; i++) {
        sort(hs[i].begin(), hs[i].end());
        hs[i].resize(unique(hs[i].begin(), hs[i].end()) - hs[i].begin());
        for (int j = 0; j < sz(hs[i]) - 1; j++) {
            int u = mapka[{i, hs[i][j]}], v = mapka[{i, hs[i][j + 1]}];
            int w = hs[i][j + 1] - hs[i][j];
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }
    }

    set<pii> setik;
    setik.insert({0, mapka[{S, 0}]});
    vector<int> dist(N, OO);
    dist[mapka[{S, 0}]] = 0;

    while (!setik.empty()) {
        pii cur = *setik.begin(); setik.erase(setik.begin());
        int dst = cur.first, v = cur.second;
        if (dst > dist[v]) continue;

        for (auto &to : g[v]) {
            if (dst + to.second < dist[to.first]) {
                dist[to.first] = dst + to.second;
                setik.insert({dist[to.first], to.first});
            }
        }
    }

    return dist[mapka[{F, 0}]];
}

/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

/*
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
*/

/*
g++ -std=gnu++14 -O2 -Wall -pipe -static -o "walk" "grader.cpp" "walk.cpp"
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 109908 KB Output is correct
2 Correct 26 ms 109912 KB Output is correct
3 Correct 25 ms 109904 KB Output is correct
4 Incorrect 25 ms 109916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 109916 KB Output is correct
2 Correct 26 ms 109908 KB Output is correct
3 Correct 1548 ms 243676 KB Output is correct
4 Correct 1564 ms 262560 KB Output is correct
5 Correct 1110 ms 243784 KB Output is correct
6 Correct 901 ms 229100 KB Output is correct
7 Incorrect 1039 ms 243780 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 125580 KB Output is correct
2 Runtime error 2374 ms 683312 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 125580 KB Output is correct
2 Runtime error 2374 ms 683312 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 109908 KB Output is correct
2 Correct 26 ms 109912 KB Output is correct
3 Correct 25 ms 109904 KB Output is correct
4 Incorrect 25 ms 109916 KB Output isn't correct
5 Halted 0 ms 0 KB -