Submission #1076343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076343		j_vdd16	Sky Walking (IOI19_walk)	C++17	24 / 100	2273 ms	1048576 KiB

walk

#include "walk.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

struct SegTree {
    int n, N;
    vi tree;
    int def = LLONG_MAX / 2;

    SegTree(vi values) {
        n = values.size();
        N = 1;
        while (N < n) N *= 2;

        tree = vi(2 * N, def);
        loop(i, n) {
            tree[N + i] = values[i];
        }

        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
    }

    int merge(int a, int b) {
        return min(a, b);
    }

    void set(int idx, int v) {
        idx += N;
        tree[idx] = v;
        idx /= 2;

        while (idx) {
            tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
            idx /= 2;
        }
    }

    int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }

        if (tr <= l || tl >= r) {
            return def;
        }

        if (tl >= l && tr <= r) {
            return tree[i];
        }

        int tm = (tl + tr) / 2;
        return merge(get(l, r, i * 2, tl, tm), get(l, r, i * 2 + 1, tm, tr));
    }
};

long long min_distance(std::vector<signed> xs, std::vector<signed> hs, std::vector<signed> ls, std::vector<signed> rs, std::vector<signed> ys, signed s, signed g) {
    int n = xs.size();
    int m = ls.size();

    vector<tuple<int, int, int>> bridges(m);
    loop(i, m) {
        bridges[i] = { ys[i], ls[i], rs[i] };
    }
    sort(all(bridges));
    sort(all(ys));

    vii buildings(n);
    loop(i, n) {
        buildings[i] = { xs[i], hs[i] };
    }
    //sort(all(buildings));

    int nodes = 0;
    vvii adj = { };

    vvii open(n), close(n);
    loop(i, m) {
        auto [y, l, r] = bridges[i];

        open[l].push_back({y, i});
        close[r].push_back({y, i});
    }

    int start = -1, end = -1;

    map<ii, ii> cur;
    for (int i = 0; i < n; i++) {
        for (auto [y, j] : open[i]) {
            cur[{y, j}] = {nodes++, xs[i]};
            adj.push_back({});
        }

        int prevNode = nodes++;
        adj.push_back({});
        if (i == s) {
            start = prevNode;
        }
        if (i == g) {
            end = prevNode;
        }

        int prevY = 0;
        for (auto& [f, f2] : cur) {
            auto [y, j] = f;
            if (y > buildings[i].second) break;

            auto& [idx, x] = f2;
            int node = idx;
            if (x != xs[i]) {
                node = nodes++;
                adj.push_back({});

                adj[idx].push_back({node, xs[i] - x});
                adj[node].push_back({idx, xs[i] - x});
            }
            adj[prevNode].push_back({ node, y - prevY });
            adj[node].push_back({ prevNode, y - prevY });

            idx = node;
            x = xs[i];

            prevY = y;
            prevNode = node;
        }

        for (auto [y, j] : close[i]) {
            cur.erase({y, j});
        }
    }

    vb vis(nodes, false);
    priority_queue<ii, vii, greater<ii>> q;
    q.push({0, start});

    int res = -1;
    while (q.size()) {
        auto [dist, node] = q.top();
        q.pop();

        if (node == end) {
            res = dist;
            break;
        }

        if (vis[node]) continue;
        vis[node] = true;

        for (auto [child, weight] : adj[node]) {
            q.push({dist + weight, child});
        }
    }

    return res;
}

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