Submission #597175

#	Time	Username	Problem	Language	Result	Execution time	Memory
597175		lcj	Sky Walking (IOI19_walk)	C++17	0 / 100	51 ms	13788 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    ll n = x.size();
    ll m = l.size();
    vector<vector<pii>> conto(n);
    vector<vector<pll>> neighbours(2*m+2);
    for (ll i = 0; i < m; i++)
    {
        conto[l[i]].push_back({y[i], i});
        conto[r[i]].push_back({y[i], i+m});
        neighbours[i].push_back({i+m, x[r[i]]-x[l[i]]});
    }
    for (ll i = 0; i < n; i++)
    {
        if (conto[i].empty()) continue;
        sort(all(conto[i]));
        auto &mconto = conto[i];
        if (i == s && !mconto.empty()) {
            neighbours[2*m].push_back({mconto[0].se, mconto[0].fi});
        }
        if (i == g && !mconto.empty()) {
            neighbours[mconto.back().se].push_back({2*m+1, mconto.back().fi});
        }
        for (ll j = 0; j < conto[i].size()-1; j++)
        {
            neighbours[mconto[j].se].push_back({mconto[j+1].se, mconto[j+1].fi-mconto[j].fi});
            neighbours[mconto[j+1].se].push_back({mconto[j].se, mconto[j+1].fi-mconto[j].fi});
        }
    }
    vector<ll> dist(2*m+2, 1e12);
    dist[2*m] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    pq.push({0, 2*m});
    while (!pq.empty())
    {
        pll cur = pq.top();pq.pop();
        if (cur.fi > dist[cur.se]) continue;
        for (pll nn : neighbours[cur.se]) {
            if (dist[nn.fi] > cur.fi + nn.se) {
                dist[nn.fi] = cur.fi + nn.se;
                pq.push({dist[nn.fi], nn.fi});
            }
        }
    }
    if (dist[2*m+1] == 1e12) {
        return -1;
    }
    return dist[2*m+1];
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:35:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (ll j = 0; j < conto[i].size()-1; j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~

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