Submission #1210457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210457		SpyrosAliv	Sky Walking (IOI19_walk)	C++20	10 / 100	4099 ms	169912 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;

int get_idx(int val, vector<tuple<int, int, ll>> &arr, int h) {
    int idx = -1;
    int sz = arr.size();
    int lo = 0, hi = sz-1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (get<0>(arr[mid]) >= h) {
            idx = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    if (get<1>(arr[idx]) != val) return idx+1;
    return idx;
}

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}
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, 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});
        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());
        pq.pop();
        int idx = get_idx(skyline, inter[build], y[skyline]);
        if (get<2>(inter[build][idx]) != dis) continue;
        int sz = inter[build].size();
        for (auto [nxtBuild, idx2]: foundIn[skyline]) {
            if (nxtBuild == build || h[nxtBuild] < y[skyline]) continue;
            //int idx2 = get_idx(skyline, inter[nxtBuild], y[skyline]);
            ll dis2 = abs(x[build] - x[nxtBuild]);
            if (dis2 + dis < get<2>(inter[nxtBuild][idx2])) {
                pq.push({dis2 + dis, nxtBuild, skyline});
                inter[nxtBuild][idx2] = {y[skyline], skyline, dis + dis2};
            }
        }
        /*
        if (l[skyline] < build) {
            
        }
        if (r[skyline] > build) {
            int idx2 = get_idx(skyline, inter[build+1], y[skyline]);
            ll dis2 = x[build+1] - x[build];
            if (dis2 + dis < get<2>(inter[build + 1][idx2])) {
                pq.push({dis2 + dis, build+1, skyline});
                inter[build + 1][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});
                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});
                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