Submission #410417

#	Time	Username	Problem	Language	Result	Execution time	Memory
410417		Tc14	Sky Walking (IOI19_walk)	C++17	24 / 100	4090 ms	616292 KiB

walk

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;

ll min_distance(ve<int> X, ve<int> H, ve<int> L, ve<int> R, ve<int> Y, int s, int g) {

    int n = (int)X.size();
    int m = (int)L.size();

    ve<tuple<int, int, int>> E;
    ve<ve<pii>> S(n);
    ve<pii> P(m, {-1, -1});
    ve<ll> D;
    ve<ve<pair<int, ll>>> G(n);
    priority_queue<pair<ll, int>, ve<pair<ll, int>>, greater<pair<ll, int>>> pq;

    for (int i = 0; i < n; i++) {
        S[i].push_back({i, 0});
        E.push_back({i, 1, -1});
    }

    for (int i = 0; i < m; i++) {
        E.push_back({L[i], 0, i});
        E.push_back({R[i], 2, i});
    }
    sort(E.begin(), E.end());

    set<pii> A;
    for (tuple<int, int, int> e : E) {

        if (get<1>(e) == 0) {
            int j = get<2>(e);
            A.insert({Y[j], j});
        }
        else if (get<1>(e) == 1) {

            int i = get<0>(e);
            for (pii a : A) {
                int j, y;
                tie(y, j) = a;
                if (y > H[i]) break;

                int u = (int)G.size();
                G.push_back({});

                if (P[j].first != -1) {
                    ll w = X[i] - P[j].second;
                    int v = P[j].first;
                    G[u].push_back({v, w});
                    G[v].push_back({u, w});
                }
                P[j] = {u, X[i]};

                S[i].push_back({u, y});
            }

        }
        else {
            int j = get<2>(e);
            A.erase({Y[j], j});
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < (int)S[i].size(); j++) {
            ll w = S[i][j].second - S[i][j - 1].second;
            int u = S[i][j].first;
            int v = S[i][j - 1].first;
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }
    }

    D = ve<ll>(G.size(), LLINF);
    pq.push({0, s});

    while (!pq.empty()) {
        int u;
        ll d;
        tie(d, u) = pq.top();
        pq.pop();

        if (D[u] != LLINF) continue;
        D[u] = d;

        for (pair<int, ll> e : G[u]) {
            pq.push({d + e.second, e.first});
        }
    }

    if (D[g] == LLINF) return -1;
    else return D[g];
}

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