oj.uz

Submission #415435

# Submission time Handle Problem Language Result Execution time Memory
415435 2021-06-01T05:50:30 Z wiwiho Sky Walking (IOI19_walk) C++14
0 / 100
 1391 ms 147792 KB 
#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()

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<>());
}

int lst = -1;
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;
            if(lst != -1) addedge(lst, y, i.S, y);
            lst = 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++){
        lst = -1;
        bridge(tl[i], tr[i], ty[i], 0, n - 1, 0);
    }

    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1391 ms 147792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 17012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 17012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -