Submission #599728

#	Time	Username	Problem	Language	Result	Execution time	Memory
599728		Johann	Sky Walking (IOI19_walk)	C++14	0 / 100	4074 ms	747080 KiB

walk

// #include "walk.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef tuple<int, int, int> tiii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int maxN = 10005;
const ll INF = 1e18;

ll djikstra(vvpii & adj, int s, int g) {
    int n = sz(adj);
    vi dist(n, INF);
    priority_queue<pii, vpii, greater<pii>> q;
    q.push({ s, 0 });
    while (!q.empty()) {
        ll v,d;
        tie(v,d) = q.top(); q.pop();
        if (dist[v] <= d) continue;
        dist[v] = d;
        for (pii e : adj[v]) {
            ll u,dd;
            tie(u,dd) = e;
            if (dist[u] == INF) q.push({ u, d + dd});
        }
    }
    return (dist[g] == INF) ? -1 : dist[g];
}

ll min_distance(vpii & B, vtiii &S, int s, int g) {

    int n = sz(B);
    int m = sz(S);
    set<pii> bu; // Häuser nach Positions
    vpii BnachH(n); // häuser nach Höhe
    F0R(i,n) bu.insert({i, i });
    F0R(i,n) BnachH[i] = { B[i].second, i };
    sort(all(BnachH), [&](pii & a, pii & b) { return a > b; });
    sort(all(S), [&](tiii &a, tiii &b) { return get<2>(a) > get<2>(b); }); // Segmente nach Höhe

    vector<set<int>> heightsOnBuildings(n);
    F0R(i,n) heightsOnBuildings[i].insert(0), heightsOnBuildings[i].insert(B[i].second);
    vvi buildingsOnSegment(m);

    F0R(i, m) {
        tiii seg = S[i];
        int l, r, y;
        tie(l, r, y) = seg;
        while (BnachH.back().first < y) {
            int idx = BnachH.back().second;
            bu.erase({ B[idx].first, idx } );
            BnachH.pop_back();
        }
        for (auto it = bu.lower_bound({l, -1}); it != bu.end() && it->first <= r; ++it) {
            int idx = it->second;
            heightsOnBuildings[idx].insert(y);
            buildingsOnSegment[i].push_back(idx);
        }
    }

    vvpii adj;
    map<pii, int> nodes;
    int idx = 0;
    F0R(i,n) {
        int last = -1, lastH = -1;
        for (int y : heightsOnBuildings[i]) {
            nodes[{i, y}] = idx;
            adj.push_back(vpii());
            if (last != -1) {
                adj[last].push_back({ idx, abs(y - lastH) });
                adj[idx].push_back({ last, abs(y - lastH) });
            }
            last = idx;
            lastH = y;
            idx++;
        }
    }

    F0R(i,m) {
        int l,r,y;
        tie(l,r,y) = S[i];

        int last = -1;
        for (int b : buildingsOnSegment[i]) {
            if (last != -1) {
                int dist = abs(B[last].first - B[b].first);
                int i1 = nodes[{ b, y }], i2 = nodes[{ last, y }];
                adj[i1].push_back({ i2, dist });
                adj[i2].push_back({ i1, dist });
            }
            last = b;
        }
    }

    return djikstra(adj, nodes[{s,0}], nodes[{g,0}]);
}

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) {
// ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n = sz(x), m = sz(l);
    vtiii segs(m);
    vpii B(n);
    F0R(i, n) B[i] = {x[i], h[i]};
    F0R(i, m) segs[i] = {l[i], r[i], y[i]};
    return min_distance(B, segs, s, g);
}

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