제출 #1242738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242738		Boas	Sky Walking (IOI19_walk)	C++20	10 / 100	4094 ms	1114112 KiB

walk

#include "walk.h"

// #pragma GCC optimize("trapv")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define loop(n, i) for (int i = 0; i < n; i++)
#define pb push_back
#define sz(x) (int)(x).size()

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<int32_t> vi32;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef map<int, int> mii;

int INF = 1e18;

int min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g)
{
    int n = sz(x), m = sz(l);
    vector<map<int, vi>> adj(n);
    loop(m, i)
    {
        for (int p = l[i]; p <= r[i]; p++)
        {
            if (h[p] < y[i])
                continue;
            for (int p2 = l[i]; p2 <= r[i]; p2++)
            {
                if (h[p2] < y[i])
                    continue;
                if (p == p2)
                    continue;
                adj[p][y[i]].pb(p2);
            }
        }
    }
    priority_queue<iii, vector<iii>, greater<iii>> q;
    vector<unordered_map<int, int>> disList(n);
    auto dis = [&](int p, int y) -> int
    {
        if (disList[p].count(y))
            return disList[p][y];
        return INF;
    };
    q.push({0, s, 0});
    while (!q.empty())
    {
        auto [d, p, y] = q.top();
        q.pop();
        if (dis(p, y) < d)
            continue;
        disList[p][y] = d;
        for (int p2 : adj[p][y])
        {
            int d2 = d + abs(x[p2] - x[p]);
            if (d2 < dis(p2, y))
            {
                disList[p2][y] = d2;
                q.push({d2, p2, y});
            }
        }
        auto nxt = adj[p].upper_bound(y);
        if (nxt != adj[p].end())
        {
            int y2 = nxt->first;
            int d2 = d + abs(y2 - y);
            if (d2 < dis(p, y2))
            {
                disList[p][y2] = d2;
                q.push({d2, p, y2});
            }
        }
        if (prev(nxt) != adj[p].begin())
        {
            nxt = prev(prev(nxt));
            int y2 = nxt->first;
            int d2 = d + abs(y2 - y);
            if (d2 < dis(p, y2))
            {
                disList[p][y2] = d2;
                q.push({d2, p, y2});
            }
        }
    }
    int res = INF;
    for (auto [y, adjY] : adj[g])
    {
        res = min(res, dis(g, y) + y);
    }
    if (res == INF)
        return -1;
    return res;
}

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