Submission #977936

#	Time	Username	Problem	Language	Result	Execution time	Memory
977936		opPO	Sky Walking (IOI19_walk)	C++14	0 / 100	2374 ms	683312 KiB

walk

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43