Submission #703190

#	Time	Username	Problem	Language	Result	Execution time	Memory
703190		qwerasdfzxcl	Sky Walking (IOI19_walk)	C++17	100 / 100	2310 ms	182152 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
constexpr ll INF = 4e18;
constexpr int MAXN = 2002000;

int n, m;
vector<int> X, H, L, R, Y;
map<int, vector<pii>> Z;

struct Event{
    int l, r, y, typ;
    Event(){}
    Event(int _l, int _r, int _y, int _typ): l(_l), r(_r), y(_y), typ(_typ) {}
};

struct Graph{
    map<pii, int> V;
    vector<pii> adj[MAXN];
    ll dist[MAXN];
    int sz;

    int add_vertex(int x, int y){
        pii p(x, y);
        if (V[p]) return V[p];
        //printf(" add vertex: %d %d\n", x, y);
        V[p] = ++sz;

        assert(sz<MAXN);
        return sz;
    }

    void add_edge(int x1, int y1, int x2, int y2){
        //printf(" add edge: %d %d <-> %d %d\n", x1, y1, x2, y2);
        pii p1(x1, y1), p2(x2, y2);
        int i1 = add_vertex(x1, y1), i2 = add_vertex(x2, y2);
        int d = abs(x1-x2) + abs(y1-y2);

        adj[i1].emplace_back(i2, d);
        adj[i2].emplace_back(i1, d);
    }

    vector<pii> get_vertex(){
        vector<pii> ret;
        for (auto &[x, y]:V) ret.push_back(x);
        return ret;
    }

    ll calc(int s, int e){
        fill(dist+1, dist+sz+1, INF);
        dist[s] = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.emplace(dist[s], s);

        while(!pq.empty()){
            auto [d, cur] = pq.top(); pq.pop();
            if (d > dist[cur]) continue;
            assert(dist[cur] == d);
            for (auto &[nxt, e]:adj[cur]) if (dist[nxt] > dist[cur] + e){
                dist[nxt] = dist[cur] + e;
                pq.emplace(dist[nxt], nxt);
            }
        }

        return dist[e]==INF?-1:dist[e];
    }
}G;

int h(int x){
    int idx = lower_bound(X.begin(), X.end(), x) - X.begin();
    return H[idx];
}

void f(int x){
    //printf("\n f %d\n", x);
    vector<Event> E;
    for (int i=0;i<n;i++) E.emplace_back(X[i], X[i], H[i], 0);
    for (int i=0;i<m;i++) E.emplace_back(L[i], R[i], Y[i], -1);
    sort(E.begin(), E.end(), [&](const Event &a, const Event &b){return tie(a.y, a.typ) > tie(b.y, b.typ);});

    set<int> st;
    for (auto &[l, r, y, typ]:E){
        //printf("  %d %d %d %d\n", l, r, y, typ);
        if (typ==0) {st.insert(l); continue;}
        if (r<x || x<l) continue;

        auto iterL = st.upper_bound(x);
        auto iterR = st.lower_bound(x);
        if (iterL!=st.begin() && *prev(iterL) >= l) G.add_vertex(*--iterL, y);
        if (iterR!=st.end() && *iterR <= r) G.add_vertex(*iterR, y);
    }
}

void add_vertical(){
    //printf("\n vertical\n");
    auto V = G.get_vertex();
    vector<Event> E;
    multiset<pii> st;

    for (int i=0;i<m;i++){
        E.emplace_back(L[i], Y[i], i, 0);
        E.emplace_back(R[i], Y[i], i, 2);
    }
    for (auto &[x, y]:V) E.emplace_back(x, y, 0, 1);
    sort(E.begin(), E.end(), [&](const Event &a, const Event &b){return tie(a.l, a.typ) < tie(b.l, b.typ);});

    for (auto &[x, y, i, typ]:E){
        if (typ==0) st.emplace(y, i);
        else if (typ==2) st.erase(st.find(pii(y, i)));
        else{
            auto iter = st.lower_bound(pii(y, i));
            if (y==0){
                if (iter!=st.end() && iter->first <= h(x)) G.add_edge(x, y, x, iter->first);
                continue;
            }
            assert(iter!=st.end());

            if (iter!=st.begin()) G.add_edge(x, y, x, prev(iter)->first);
            if (next(iter)!=st.end() && next(iter)->first <= h(x)) G.add_edge(x, y, x, next(iter)->first);
        }
    }
}

void add_horizontal(){
    //printf("\n horizontal\n");
    auto V = G.get_vertex();
    sort(V.begin(), V.end(), [&](pii x, pii y){return tie(x.second, x.first) < tie(y.second, y.first);});

    for (int i=1;i<(int)V.size();i++) if (V[i-1].second == V[i].second){
        int x1 = V[i-1].first, x2 = V[i].first, y = V[i].second;

        auto iter = lower_bound(Z[y].begin(), Z[y].end(), pii(x2, -1));
        if (iter==Z[y].begin()) continue;
        --iter;

        if (iter->first <= x1 && x2 <= iter->second) G.add_edge(x1, y, x2, y);
    }
}

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 P1, int P2) {
	n = X.size(); m = L.size();
	P1 = X[P1], P2 = X[P2];
	for (auto &x:L) x = X[x];
	for (auto &x:R) x = X[x];

	::X = X, ::H = H, ::L = L, ::R = R, ::Y = Y;
	for (int i=0;i<m;i++){
        Z[Y[i]].emplace_back(L[i], R[i]);
	}
	for (auto iter=Z.begin();iter!=Z.end();iter++) sort(iter->second.begin(), iter->second.end());

	G.add_vertex(P1, 0);
	G.add_vertex(P2, 0);

    for (int i=0;i<m;i++){
        G.add_vertex(L[i], Y[i]);
        G.add_vertex(R[i], Y[i]);
    }

    f(P1); f(P2);
    add_vertical();
    add_horizontal();

    return G.calc(1, 2);
}

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