oj.uz

답안 #1076255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1076255 2024-08-26T12:18:57 Z j_vdd16 Sky Walking (IOI19_walk) C++17
0 / 100
 70 ms 24660 KB 
#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, int> cur;
    for (int i = 0; i < n; i++) {
        for (auto [y, j] : open[i]) {
            cur[{y, j}] = nodes++;
            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, idx] : cur) {
            auto [y, j] = f;
            if (y > buildings[i].second) break;

            int node = idx;
            if (xs[i] != xs[ls[j]]) {
                node = nodes++;
                adj.push_back({});

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

            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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 24660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -