Submission #1057535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057535		Zicrus	Sky Walking (IOI19_walk)	C++17	24 / 100	2998 ms	1048576 KiB

walk

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

typedef long long ll;

ll n, m;
vector<vector<pair<ll, ll>>> ints; // y, nodeId
vector<pair<ll, pair<ll, ll>>> bridges;
ll cnt;

vector<vector<pair<ll, ll>>> adj;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    n = x.size(); m = y.size();
    cnt = 0;
    ints = vector<vector<pair<ll, ll>>>(n);
    ints[s].push_back({0, cnt++});
    ints[g].push_back({0, cnt++});
    bridges = vector<pair<ll, pair<ll, ll>>>(m);
    for (int i = 0; i < m; i++) {
        bridges[i] = {y[i], {l[i], r[i]}};
    }
    sort(bridges.begin(), bridges.end());
    vector<vector<pair<ll, ll>>> it(m); // x, nodeId
    vector<ll> lnk(n);
    for (int i = 0; i < n; i++) lnk[i] = i+1;
    for (int j = 0; j < m; j++) {
        pair<ll, ll> p = bridges[j].second;
        ll lastCorr = -1;
        for (int i = p.first; i <= p.second; i = lnk[i]) {
            if (bridges[j].first > h[i]) continue;
            if (lastCorr != -1) {
                lnk[lastCorr] = i;
            }
            it[j].push_back({x[i], cnt});
            ints[i].push_back({bridges[j].first, cnt++});
            lastCorr = i;
        }
    }

    adj = vector<vector<pair<ll, ll>>>(cnt); // dist, nodeId
    for (auto &e : ints) { // SIGNAL 11
        if (e.size() < 2) continue;
        for (int i = 0; i < e.size()-1; i++) {
            ll dist = e[i+1].first - e[i].first;
            adj[e[i].second].push_back({dist, e[i+1].second});
            adj[e[i+1].second].push_back({dist, e[i].second});
        }
    }
    for (auto &e : it) {
        for (int i = 0; i < e.size()-1; i++) {
            adj[e[i].second].push_back({e[i+1].first - e[i].first, e[i+1].second});
            adj[e[i+1].second].push_back({e[i+1].first - e[i].first, e[i].second});
        }
    }

    priority_queue<pair<ll, ll>> q;
    q.push({0, 0});
    vector<ll> dist(cnt, 1ll << 62ll);
    dist[0] = 0;
    vector<bool> vst(cnt);
    while (!q.empty()) {
        ll cur = q.top().second; q.pop();
        if (vst[cur]) continue;
        vst[cur] = true;
        for (auto &e : adj[cur]) {
            dist[e.second] = min(dist[e.second], dist[cur] + e.first);
            q.push({-dist[e.second], e.second});
        }
    }

    return dist[1] == 1ll << 62ll ? -1 : dist[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:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; i < e.size()-1; i++) {
      |                         ~~^~~~~~~~~~~~
walk.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int i = 0; i < e.size()-1; i++) {
      |                         ~~^~~~~~~~~~~~

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