Submission #1044032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044032		yanb	Sky Walking (IOI19_walk)	C++14	0 / 100	3620 ms	1048576 KiB

walk

#include <bits/stdc++.h>

using namespace std;
    
#define int long long
#define pii pair<long long, long long>

int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, 
				 vector<signed> r, vector<signed> y, signed v_start, signed v_end) {
    int n_build = x.size(), n_sky = y.size();
    vector<pii> xy; // {x, y}
	vector<vector<pii>> stick(n_build); // {y, id}
    vector<vector<pii>> g; // {v, dst}

	for (int i = 0; i < n_sky; i++) {
        for (int b = l[i]; b <= r[i]; b++) {
            int lst;
            if (y[i] <= h[b]) {
                stick[b].push_back({y[i], xy.size()});
                xy.push_back({x[b], y[i]});
                g.emplace_back();
                if (b != l[i]) {
                    g.back().push_back({xy.size() - 2, x[b] - x[lst]});
                    g[xy.size() - 2].push_back({xy.size() - 1, x[b] - x[lst]});
                }
                lst = b;
            }
        }
    }

    for (int i = 0; i < n_build; i++) {
        stick[i].push_back({0, g.size()});
        g.emplace_back();
        xy.push_back({x[i], 0});
        sort(stick[i].begin(), stick[i].end());
        for (int j = 0; j < (int) stick[i].size() - 1; j++) {
            int dst = stick[i][j + 1].first - stick[i][j].first;
            g[stick[i][j].second].push_back({stick[i][j + 1].second, dst});
            g[stick[i][j + 1].second].push_back({stick[i][j].second, dst});
        }
    }

    int n_vert = xy.size();

    vector<int> d(n_vert, 1e17);
    d[n_vert - n_build + v_start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, n_vert - n_build + v_start});

    while (!q.empty()) {
        auto [dv, v] = q.top();
        q.pop();
        if (d[v] < dv) continue;
        for (auto [u, dvu] : g[v]) {
            if (dvu + dv < d[u]) {
                d[u] = dvu + dv;
                q.push({d[u], u});
            }
        }
    } 

    return d[n_vert - n_build + v_end];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:51:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         auto [dv, v] = q.top();
      |              ^
walk.cpp:54:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         for (auto [u, dvu] : g[v]) {
      |                   ^
walk.cpp:23:68: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |                     g.back().push_back({xy.size() - 2, x[b] - x[lst]});
      |                                                                    ^

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