Submission #1238053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238053		Ghulam_Junaid	Sky Walking (IOI19_walk)	C++20	0 / 100	1782 ms	273436 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
// #include "grader.cpp"
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
ll dist[N];
vector<pair<ll, int>> g[N];
map<int, pair<int, int>> rev;

void dijkstra(int v){
    memset(dist, 31, sizeof dist);
    dist[v] = 0;

    set<pair<ll, int>> st;
    st.insert({0, v});

    while (!st.empty()){
        auto [d, v] = *st.begin();
        // cout << rev[v].first << " " << rev[v].second << " :: " << d << endl;
        st.erase(st.begin());

        for (auto [w, u] : g[v]){
            if (dist[u] > dist[v] + w){
                st.erase({dist[u], u});
                dist[u] = dist[v] + w;
                st.insert({dist[u], u});
            }
        }
    }
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e) {
    int n = x.size(), m = l.size();
    int cur = 0;
    map<pair<int, int>, int> id;
    vector<int> vec[n];
    for (int i = 0; i < m; i ++){
        vector<int> buildings;
        for (int j = l[i]; j <= r[i]; j ++){
            if (h[j] < y[i]) continue;
            buildings.push_back(j);
            vec[j].push_back(y[i]);
            id[{j, y[i]}] = cur++;
        }

        for (int j = 0; j + 1 < buildings.size(); j ++){
            int u = id[{buildings[j], y[i]}], v = id[{buildings[j + 1], y[i]}], w = x[buildings[j + 1]] - x[buildings[j]];
            g[u].push_back({w, v});
            g[v].push_back({w, u});
        }
    }
    for (int i = 0; i < n; i ++){
        id[{i, 0}] = cur++;
        vec[i].push_back(0);
        sort(vec[i].begin(), vec[i].end());

        for (int j = 0; j + 1 < vec[i].size(); j ++){
            int u = id[{i, vec[i][j]}], v = id[{i, vec[i][j + 1]}], w = vec[i][j + 1] - vec[i][j];
            g[u].push_back({w, v});
            g[v].push_back({w, u});
        }
    }

    for (auto [P, i] : id)
        rev[i] = P;

    dijkstra(id[{s, 0}]);
    if (dist[id[{e, 0}]] > 1e18)
        dist[id[{e, 0}]] = -1;
	return dist[id[{e, 0}]];
}

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