제출 #434251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434251		emil_physmath	Sky Walking (IOI19_walk)	C++17	39 / 100	4061 ms	406044 KiB

walk

#define BUGO(x) cerr << #x << " -> " << (x) << endl;
#include "walk.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
using llong = long long;

vector<pair<int, int>> nei[6900'000];
llong dist[6900'000];

const llong inf = 69'000'000'000'000'000LL;
llong Dijkstra(int s, int e)
{
    fill(dist, dist + 6900'000, inf);
    priority_queue<pair<llong, int>> q;
    q.push({dist[s] = 0, s});
    while (q.size())
    {
        int v = q.top().second;
        llong d = -q.top().first;
        q.pop();
        if (dist[v] != d) continue;
        for (auto to: nei[v])
            if (d + to.second < dist[to.first])
                q.push({-(dist[to.first] = d + to.second), to.first});
    }
    return dist[e] == inf ? -1 : dist[e];
}

map<int, int> nodeOf[100'000];
llong dp[100'000];
struct Comp {
    static vector<int>* h_;
    bool operator()(int l, int r) const {
        return h_->at(l) < h_->at(r);
    }
};
vector<int>* Comp::h_;
long long min_distance(std::vector<int> x, std::vector<int> y, std::vector<int> l, std::vector<int> r,
std::vector<int> h, int s, int e) {
    int n = x.size();
    int m = l.size();
    if ((n <= 50 && m <= 50) || y != vector<int>(n, y[0]))
    {
        int nodes = 0;
        for (int i = 0; i < n; ++i)
            nodeOf[i][y[i]] = nodes++;
        nodeOf[s][0] = nodes++;
        nodeOf[e][0] = nodes++;
        vector<int> towers(n);
        iota(towers.begin(), towers.end(), 0);
        sort(towers.begin(), towers.end(), [&](int l, int r) {
            return y[l] < y[r];
        });
        vector<int> bridges(m);
        iota(bridges.begin(), bridges.end(), 0);
        sort(bridges.begin(), bridges.end(), [&](int l, int r) {
            return h[l] < h[r];
        });
        set<int> activeTowers;
        for (int tch = m - 1; tch >= 0; --tch)
        {
            int j = bridges[tch];
            while (towers.size() && y[towers.back()] >= h[j]) {
                activeTowers.insert(towers.back());
                towers.pop_back();
            }
            int lt = -1;
            for (auto it = activeTowers.lower_bound(l[j]); it != activeTowers.end() && *it <= r[j]; ++it)
            {
                int i = *it;
                if (!nodeOf[i].count(h[j]))
                    nodeOf[i][h[j]] = nodes++;
                if (lt != -1) {
                    int u = nodeOf[i][h[j]];
                    int v = nodeOf[lt][h[j]];
                    nei[u].push_back({v, x[i] - x[lt]});
                    nei[v].push_back({u, x[i] - x[lt]});
                }
                lt = i;
            }
        }
        for (int i = 0; i < n; ++i)
        {
            int ltHei = -1;
            for (auto [hei, node]: nodeOf[i])
            {
                if (ltHei != -1) {
                    int u = nodeOf[i][ltHei];
                    int v = node;
                    nei[u].push_back({v, hei - ltHei});
                    nei[v].push_back({u, hei - ltHei});
                }
                ltHei = hei;
            }
        }
        return Dijkstra(n, n + 1);
    }

    l.push_back(-1);
    r.push_back(0);
    h.push_back(0);
    ++m;
    fill(dp, dp + m, inf);
    dp[m - 1] = 0;
    vector<int> bridges(m);
    iota(bridges.begin(), bridges.end(), 0);
    sort(bridges.begin(), bridges.end(), [&r](int i, int j) {
        return r[i] < r[j];
    });

    vector<pair<int, int>> bridgesUpd;
    for (int j = 0; j < m; ++j) {
        bridgesUpd.push_back({l[j], j});
        bridgesUpd.push_back({r[j], -j});
    }
    sort(bridgesUpd.begin(), bridgesUpd.end());

    Comp::h_ = &h;
    set<int, Comp> activeBridges;
    int j = 0;
    for (int i: bridges)
    {
        if (dp[i] == inf) continue;
        while (j < bridgesUpd.size() && bridgesUpd[j].first <= r[i]) {
            // BUGO(bridgesUpd[j].first)
            int upd = bridgesUpd[j++].second;
            if (upd > 0 || (!upd && !activeBridges.count(upd))) activeBridges.insert(upd);
            else activeBridges.erase(-upd);
        }
        auto it = activeBridges.lower_bound(i);
        if (it != activeBridges.end())
            dp[*it] = min(dp[*it], dp[i] + x[r[*it]] - x[r[i]] + h[*it] - h[i]);
        if (it != activeBridges.begin()) {
            --it;
            dp[*it] = min(dp[*it], dp[i] + x[r[*it]] - x[r[i]] + h[i] - h[*it]);
        }
    }
    llong ans = inf;
    for (int j = 0; j < m; ++j)
        if (r[j] == n - 1)
            ans = min(ans, dp[j] + h[j]);
    return ans == inf ? -1 : ans;
}

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         while (j < bridgesUpd.size() && bridgesUpd[j].first <= r[i]) {
      |                ~~^~~~~~~~~~~~~~~~~~~

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