Submission #1063745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063745		aaaaaarroz	Sky Walking (IOI19_walk)	C++17	24 / 100	3903 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:31: 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:31: 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