Submission #897285

#	Time	Username	Problem	Language	Result	Execution time	Memory
897285		vgtcross	Sky Walking (IOI19_walk)	C++17	57 / 100	1460 ms	1048576 KiB

walk

#include <bits/stdc++.h>

#define MODE 0

#define fi first
#define se second

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
    int n = x.size();
    int m = y.size();
    if (s == 0 && g == n-1) {
        map<int, ll> dis;
        map<int, int> f;
        dis[0] = 0;
        f[0] = 1;
        vector<array<int, 3>> v = {{0, 1, 0}, {n-1, 0, 0}};
        for (int i = 0; i < m; ++i) {
            v.push_back({l[i], 0, y[i]});
            v.push_back({r[i], 1, y[i]});
        }
        sort(v.begin(), v.end());
        for (auto &a : v) {
            if (a[1] == 0) {
                ++f[a[2]];
                if (!dis.count(a[2])) dis[a[2]] = 1e18;
                auto it = dis.find(a[2]);
                if (++it != dis.end()) dis[a[2]] = min(dis[a[2]], it->se + it->fi - a[2]);
                it = dis.find(a[2]);
                if (it-- != dis.begin()) dis[a[2]] = min(dis[a[2]], it->se + a[2] - it->fi);
            } else if (--f[a[2]] == 0) {
                f.erase(a[2]);
                dis.erase(a[2]);
            }
        }
        return dis[0] >= 1e17 ? -1 : x[n-1] - x[0] + dis[0];
    } else {
        vector<array<int, 3>> items;
        for (int i = 0; i < n; ++i) items.push_back({h[i], 1, i});
        for (int i = 0; i < m; ++i) items.push_back({y[i], 0, i});
        sort(items.rbegin(), items.rend());
        set<int> bds;
        int w = 0;
        vector<vector<pll>> adj;
        vector<pll> crd;
        vector<int> bi(n, -1), ri(m, -1);
        auto add_edge = [&](int p, int q) {
            ll d = abs(crd[p].fi - crd[q].fi) + abs(crd[p].se - crd[q].se);
            adj[p].push_back({d, q});
            adj[q].push_back({d, p});
        };
        for (auto &a : items) {
            if (a[1] == 1) bds.insert(a[2]);
            else {
                for (auto it = bds.find(l[a[2]]); true; ++it) {
                    crd.push_back({x[*it], a[0]});
                    adj.push_back({});
                    if (bi[*it] != -1) add_edge(bi[*it], w);
                    if (ri[a[2]] != -1) add_edge(ri[a[2]], w);
                    bi[*it] = w;
                    ri[a[2]] = w;
                    w++;
                    if (*it == r[a[2]]) break;
                }
            }
        }
        int e = w++;
        int f = w++;
        crd.push_back({x[s], 0});
        crd.push_back({x[g], 0});
        adj.push_back({});
        adj.push_back({});
        if (bi[s] != -1) add_edge(e, bi[s]);
        if (bi[g] != -1) add_edge(f, bi[g]);
        priority_queue<pll> pq;
        pq.push({0, e});
        vector<bool> vis(w, 0);
        while (pq.size()) {
            auto p = pq.top();
            pq.pop();
            if (vis[p.se]) continue;
            vis[p.se] = 1;
            
            if (p.se == f) return -p.fi;
            
            for (auto v : adj[p.se]) if (!vis[v.se]) {
                pq.push({p.fi - v.fi, v.se});
            }
        }
        return -1;
    }
}

#if MODE
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n), h(n);
    vector<int> l(m), r(m), y(m);
    for (int i = 0; i < n; ++i) cin >> x[i] >> h[i];
    for (int i = 0; i < m; ++i) cin >> l[i] >> r[i] >> y[i];
    int s, g;
    cin >> s >> g;
    cout << min_distance(x, h, l, r, y, s, g) << '\n';
}
#endif

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