Submission #1238081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238081		Ghulam_Junaid	Sky Walking (IOI19_walk)	C++20	10 / 100	4096 ms	459700 KiB

walk

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

typedef long long ll;

const int N = 2e6 + 10;
ll dist[N], vis[N];
vector<pair<ll, int>> g[N];

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

    priority_queue<pair<ll, int>> pq;
    pq.push({0, v});

    while (!pq.empty()){
        auto [d, v] = pq.top();
        pq.pop();
        if (vis[v]) continue;
        vis[v] = 1;

        for (auto [w, u] : g[v]){
            if (dist[u] > dist[v] + w){
                dist[u] = dist[v] + w;
                pq.push({-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 = 1;
    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]);
            if (id.find({j, y[i]}) == id.end())
                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 ++){
        if (id.find({i, 0}) == id.end())
            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});
        }
    }

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

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