oj.uz

Submission #597175

# Submission time Handle Problem Language Result Execution time Memory
597175 2022-07-15T16:35:59 Z lcj Sky Walking (IOI19_walk) C++17
0 / 100
 51 ms 13788 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 13788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 13788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -