제출 #1210455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210455		SpyrosAliv	Sky Walking (IOI19_walk)	C++20	10 / 100	4099 ms	115800 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 (int nxtBuild = l[skyline]; nxtBuild <= r[skyline]; nxtBuild++) {
            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;
}
/*
int main() {
    cin >> n >> m;
    vector<int> x(n), h(n), l(m), r(m), y(m);
    int s, g;
    for (int i = 0; i < n; i++) cin >> x[i] >> h[i];
    for (int i = 0; i < m; i++) cin >> l[i] >> r[i] >> y[i];
    cin >> s >> g;
    cout << min_distance(x, h, l, r, y, s, g) << "\n";
}*/

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