Submission #415441

#	Time	Username	Problem	Language	Result	Execution time	Memory
415441		wiwiho	Sky Walking (IOI19_walk)	C++14	24 / 100	4054 ms	594608 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define lsort(a) sort(iter(a))

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

const ll MAX = 1LL << 60;

int n, m;

vector<int> x, h, tl, tr, ty;
int sv, gv;

int ts = 1;
vector<vector<pll>> g;
vector<map<int, int>> vid;

int getid(int i, int t){
    if(vid[i][t] == 0) vid[i][t] = ts++, g.eb();
    return vid[i][t];
}

void addedge(int i1, int t1, int i2, int t2){
    int u = getid(i1, t1);
    int v = getid(i2, t2);
    //cerr << "addedge " << i1 << " " << t1 << " " << i2 << " " << t2 << "\n";
    g[u].eb(mp(v, abs(x[i1] - x[i2]) + abs(t1 - t2)));
    g[v].eb(mp(u, abs(x[i1] - x[i2]) + abs(t1 - t2)));
}

vector<vector<pii>> st;

void build(int l, int r, int id){
    if(l == r){
        st[id].eb(mp(h[l], l));
        return;
    }
    int m = (l + r) / 2;
    build(l, m, id * 2 + 1);
    build(m + 1, r, id * 2 + 2);
    st[id].resize(r - l + 1);
    merge(iter(st[id * 2 + 1]), iter(st[id * 2 + 2]), st[id].begin(), greater<>());
}

vector<int> inter;
void bridge(int l, int r, int y, int L, int R, int id){
    if(l == L && r == R){
        for(pii i : st[id]){
            if(i.F < y) break;
            inter.eb(i.S);
        }
        return;
    }
    int M = (L + R) / 2;
    if(r <= M) bridge(l, r, y, L, M, id * 2 + 1);
    else if(l > M) bridge(l, r, y, M + 1, R, id * 2 + 2);
    else{
        bridge(l, M, y, L, M, id * 2 + 1);
        bridge(M + 1, r, y, M + 1, R, id * 2 + 2);
    }
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g){

    x = _x; h = _h; tl = _l; tr = _r; ty = _y; sv = _s; gv = _g;

    n = x.size();
    m = ty.size();
    g.resize(1);
    vid.resize(n);
    st.resize(4 * n);

    build(0, n - 1, 0);

    for(int i = 0; i < m; i++){
        inter.clear();
        bridge(tl[i], tr[i], ty[i], 0, n - 1, 0);
        lsort(inter);
        //cerr << "test " << i << "  ";
        //printv(inter, cerr);
        int lst = -1;
        for(int j : inter){
            if(lst != -1) addedge(lst, ty[i], j, ty[i]);
            lst = j;
        }
    }

    getid(sv, 0);
    getid(gv, 0);

    for(int i = 0; i < n; i++){
        for(auto it = vid[i].begin(); it != vid[i].end() && next(it) != vid[i].end(); it++){
            addedge(i, it->F, i, next(it)->F);
        }
    }

    priority_queue<pll, vector<pll>, greater<>> pq;
    vector<ll> dis(ts, MAX);
    dis[getid(sv, 0)] = 0;
    pq.push(mp(0, getid(sv, 0)));

    while(!pq.empty()){
        int now = pq.top().S;
        ll d = pq.top().F;
        pq.pop();
        if(d != dis[now]) continue;
        for(pll i : g[now]){
            if(d + i.S >= dis[i.F]) continue;
            dis[i.F] = d + i.S;
            pq.push(mp(d + i.S, i.F));
        }
    }

    if(dis[getid(gv, 0)] == MAX) return -1;
    return dis[getid(gv, 0)];
}

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