Submission #600174

#	Time	Username	Problem	Language	Result	Execution time	Memory
600174		Johann	Sky Walking (IOI19_walk)	C++14	0 / 100	18 ms	4380 KiB

walk

// #include "walk.h"
// bruteForce sub 3
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef tuple<int, int, int> tiii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int maxN = 10005;
const ll INF = 1e18;

ll min_distance(vpii &B, vtiii &S, int s, int g) {
    int n = sz(B);
    int m = sz(S);
    map<ll, ll> dp;
    dp[0] = 0;

    priority_queue<pii, vpii, greater<pii>> q;
    F0R(i, m) q.push({get<0>(S[i]), -(i + 1)});
    S.push_back({0, 0, 0});
    q.push({0, m + 1});
    set<ll> ignore;

    while (!q.empty()) {
        if (sz(dp) == 0) return -1;
        int l, r, y, i, idx;
        tie(l, i) = q.top();
        q.pop();
        if (l >= g) break;
        idx = abs(i) - 1;
        tie(l, r, y) = S[idx];
        if (idx > i) { // hinzufügen
            auto it = dp.lower_bound(y);
            if (it->first == y) {
                ignore.insert(y);
            } else {
                ll v = INF;
                if (it != dp.end()) {
                    v = min(v, it->second + abs(it->first - y));
                }
                if (it != dp.begin()) {
                    --it;
                    v = min(v, it->second + abs(it->first - y));
                }
                dp[y] = v;
            }
            q.push({r, idx + 1});
        } else { // Entfernen
            auto iti = ignore.find(idx);
            if (iti == ignore.end()) { // die Linie wird nicht fortgeführt
                auto it  = dp.find(y);
                ll yy,dd; tie(yy,dd) = *it;
                if (it != dp.begin()) {
                    --it;
                    it->second = min(it->second, dd + abs(it->first - yy));
                    ++it;
                }
                ++it;
                if (it != dp.end()) {
                    it->second = min(it->second, dd + abs(it->first - yy));
                }
                --it;
                dp.erase(it);
            } else {
                ignore.erase(iti);
            }
        }
    }
    ll ans = INF;
    for (auto it = dp.begin(); it != dp.end(); ++it) {
        ans = min(ans, it->second + it->first);
    }
    return ans + B[g].first - B[s].first;
}

long long
min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s,
             int g) {
// ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n = sz(x), m = sz(l);
    if (g < s) swap(g, s);
    vtiii segs(m);
    vpii B(n);
    F0R(i, n) B[i] = {x[i], h[i]};
    F0R(i, m) segs[i] = {l[i], r[i], y[i]};
    return min_distance(B, segs, s, g);
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(vpii&, vtiii&, int, int)':
walk.cpp:24:9: warning: unused variable 'n' [-Wunused-variable]
   24 |     int n = sz(B);
      |         ^

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