Submission #198819

#	Time	Username	Problem	Language	Result	Execution time	Memory
198819		imeimi2000	Sky Walking (IOI19_walk)	C++17	10 / 100	4466 ms	287224 KiB

walk

#include "walk.h"
#include <algorithm>
#include <queue>
#include <tuple>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m;
int X[100001], H[100001];
int L[100001], R[100001], Y[100001];

llong dijkstra(int s, int e, const vector<vector<pii>> &edge) {
    const llong inf = 1e18;
    int n = int(edge.size()) - 1;
    vector<llong> D(n + 1, inf);
    priority_queue<pll> pq;
    D[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        llong x, d;
        tie(d, x) = pq.top();
        pq.pop();
        d = -d;
        if (D[x] != d) continue;
        for (pii i : edge[x]) {
            llong nd = d + i.se;
            if (nd < D[i.fs]) {
                D[i.fs] = nd;
                pq.emplace(-nd, i.fs);
            }
        }
    }
    return D[e] < inf ? D[e] : -1;
}

llong solve12(int s, int e) {
    int idx = n;
    vector<vector<pii>> P(n + 1);
    vector<int> S[20];
    for (int i = 0; i < 20; ++i) S[i] = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i) {
        P[i].emplace_back(0, i);
        S[0][i] = H[i];
    }
    for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            S[i][j] = S[i - 1][j];
            int k = j + (1 << i - 1);
            if (k <= n) S[i][j] = max(S[i][j], S[i - 1][k]);
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = L[i]; j <= R[i]; ++j) {
            if (Y[i] > H[j]) continue;
            P[j].emplace_back(Y[i], ++idx);
        }
    }
    vector<vector<pii>> edge(idx + 1);
    auto add_edge = [&](int a, int b, int c) {
        edge[a].emplace_back(b, c);
        edge[b].emplace_back(a, c);
    };
    for (int i = 1; i <= n; ++i) {
        sort(P[i].begin(), P[i].end());
        for (int j = 1; j < int(P[i].size()); ++j) {
            add_edge(P[i][j - 1].se, P[i][j].se, P[i][j].fs - P[i][j - 1].fs);
        }
    }
    for (int i = 1; i <= m; ++i) {
        int pri = -1, prx;
        for (int j = L[i]; j <= R[i]; ++j) {
            if (Y[i] > H[j]) continue;
            int it = lower_bound(P[j].begin(), P[j].end(), pii(Y[i], 0))->se;
            if (pri != -1) add_edge(pri, it, X[j] - prx);
            pri = it;
            prx = X[j];
            if (j == R[i]) break;
            for (int k = 20; k--; ) {
                if (S[k][j + 1] < Y[i]) j += 1 << k;
            }
        }
    }
    return dijkstra(s, e, edge);
}

llong solve34() {
    return -1;
}

llong min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size();
    m = l.size();
    for (int i = 1; i <= n; ++i) {
        X[i] = x[i - 1];
        H[i] = h[i - 1];
    }
    for (int i = 1; i <= m; ++i) {
        L[i] = l[i - 1] + 1;
        R[i] = r[i - 1] + 1;
        Y[i] = y[i - 1];
    }
    if (s == 0 && g == n - 1) {
        //return solve34();
    }
    return solve12(s + 1, g + 1);
}

Compilation message (stderr)

walk.cpp: In function 'llong solve12(int, int)':
walk.cpp:53:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             int k = j + (1 << i - 1);
                               ~~^~~

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