Submission #1210465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210465		SpyrosAliv	Sky Walking (IOI19_walk)	C++20	10 / 100	4142 ms	1096436 KiB

walk

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

const ll INF = 1e17;

vector<vector<pair<int, int>>> graph;
int n, m;

ll 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();
    vector<vector<tuple<int, int, ll>>> inter(n);
    for (int i = 0; i < m; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            if (h[j] < y[i]) continue;
            inter[j].push_back({y[i], i, INF});
        }
    }
    for (int i = 0; i < n; i++) sort(inter[i].begin(), inter[i].end());
    // {min distance, building, skyline index, idx}
    priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq;
    for (int i = 0; i < (int)inter[s].size(); i++) {
        int skyline = get<1>(inter[s][i]);
        pq.push({y[skyline], s, skyline, i});
        inter[s][i] = {y[skyline], skyline, y[skyline]};
    }
    vector<vector<pair<int, int>>> foundIn(m);
    for (int i = 0; i < n; i++) {
        int sz = inter[i].size();
        for (int j = 0; j < sz; j++) {
            foundIn[get<1>(inter[i][j])].push_back({i, j});
        }
    }
    while (!pq.empty()) {
        ll dis = get<0>(pq.top());
        int build = get<1>(pq.top());
        int skyline = get<2>(pq.top());
        int idx = get<3>(pq.top());
        pq.pop();
        if (get<2>(inter[build][idx]) != dis) continue;
        int sz = inter[build].size();
        int le = -1, rr = -1;
        int idxl = -1, idxr = -1;
        for (auto [nxtBuild, idx2]: foundIn[skyline]) {
            if (nxtBuild == build || h[nxtBuild] < y[skyline]) continue;
            if (nxtBuild < build) {
                idxl = idx2;
                le = nxtBuild;
            }
            if (nxtBuild > build && rr == -1) {
                rr = nxtBuild;
                idxr = idx2;
                break;
            }
        }
        if (le != -1) {
            int idx2 = idxl;
            int nxtBuild = le;
            ll dis2 = abs(x[build] - x[nxtBuild]);
            if (dis2 + dis < get<2>(inter[nxtBuild][idx2])) {
                pq.push({dis2 + dis, nxtBuild, skyline, idx2});
                inter[nxtBuild][idx2] = {y[skyline], skyline, dis + dis2};
            }
        }
        if (rr != -1) {
            int idx2 = idxr;
            int nxtBuild = rr;
            ll dis2 = abs(x[build] - x[nxtBuild]);
            if (dis2 + dis < get<2>(inter[nxtBuild][idx2])) {
                pq.push({dis2 + dis, nxtBuild, skyline, idx2});
                inter[nxtBuild][idx2] = {y[skyline], skyline, dis + dis2};
            }
        }
        if (idx + 1 < sz) {
            int skyline2 = get<1>(inter[build][idx+1]);
            ll dis2 = y[skyline2] - y[skyline];
            int idx2 = idx+1;
            if (dis2 + dis < get<2>(inter[build][idx2])) {
                pq.push({dis2 + dis, build, skyline2, idx2});
                inter[build][idx2] = {y[skyline2], skyline2, dis + dis2};
            }
        }
        if (idx > 0) {
            int skyline2 = get<1>(inter[build][idx-1]);
            ll dis2 = y[skyline] - y[skyline2];
            int idx2 = idx-1;
            if (dis2 + dis < get<2>(inter[build][idx2])) {
                pq.push({dis2 + dis, build, skyline2, idx2});
                inter[build][idx2] = {y[skyline2], skyline2, dis + dis2};
            }
        }
    }
    ll ans = INF;
    for (int i = 0; i < (int)inter[g].size(); i++) {
        ans = min(ans, get<2>(inter[g][i]) + y[get<1>(inter[g][i])]);
    }
    if (ans == INF) return -1;
    else return ans;
}

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