Submission #424536

#	Time	Username	Problem	Language	Result	Execution time	Memory
424536		Monchito	Sky Walking (IOI19_walk)	C++14	10 / 100	4080 ms	769180 KiB

walk

#include "walk.h"
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<ll, int>;

#define sz(x) (int)x.size()
#define fi first
#define se second

const int MAXN = 3e6;
const ll INF = 1e18;

int n;
vi G[MAXN]; vll W[MAXN];

void create_link(int u, int v, ll w) {
    G[u].push_back(v);
    G[v].push_back(u);
    W[u].push_back(w);
    W[v].push_back(w);
}

ll dijkstra(int s, int g) { 
    vll dist(n, INF);
    priority_queue<ii> q;
    dist[s] = 0;
    q.push( {-0, s} );

    while(!q.empty()) {
        ii p = q.top(); q.pop();
        int u = p.se;

        if(dist[u] != -p.fi) continue;

        for(int i=0; i<sz(G[p.se]); i++) {
            int v = G[p.se][i];
            ll w = W[p.se][i];

            if(-p.fi + w < dist[v]) {
                dist[v] = -p.fi + w;
                q.push( { -dist[v], v } );
            }
        }
    }

    if(dist[g] == INF) return -1;
    return dist[g];
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    n = sz(x);  
    vector<pair<int, int>> bridge, re;

    for(int i=0; i<sz(l); i++) bridge.push_back( { y[i], i } );
    sort(bridge.begin(), bridge.end());

    for(int i=0; i<n; i++) re.push_back( { 0, i } );

    for(pair<int,int> p : bridge) {
        int index = p.se;

        create_link(re[l[index]].se, n, p.fi - re[l[index]].fi);
        re[l[index]] = { p.fi, n };

        pair<int,int> current_node = { x[l[index]], n };
        n++;

        for(int i = l[index]+1; i <= r[index]; i++) {
            if(p.fi <= h[i]) {
                create_link(current_node.se, n, x[i] - current_node.fi);
                current_node = { x[i], n };
                n++;

                create_link(current_node.se, re[i].se, p.fi - re[i].fi);
                re[i] = { p.fi, current_node.se };
            }
        }
    }

    return dijkstra(s, g);
}

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