Submission #1246812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246812		sofiefu	Sky Walking (IOI19_walk)	C++20	24 / 100	4058 ms	554320 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
using namespace std;

#define int long long
#define vo vector
#define pb push_back
#define fi first 
#define se second 
#define all(x) x.begin(), x.end()
typedef vector<signed> vs;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define rep(i, a, b) for(int i=(a); i<(b);i++)
#define repd(i, a, b) for(int i=(b-1); i>=a;i--)
#define pr(x) cerr << #x << " = " << x << endl;
int const inf = 1e18, mxn = 1e5+5;
int n, m;

int min_distance(vs X, vs hei, vs L, vs R, vs Y, signed s, signed g){
    n = X.size(); m = Y.size();
    vo<pii> shei;
    rep(i, 0, n){
        shei.pb({hei[i], X[i]});
    }
    sort(all(shei));
    
    vo<pii> skys;
    rep(i, 0, m){
        skys.pb({Y[i], i});
    }
    sort(all(skys));
    
    // find all intersections for a skywalk with buildings
    map<int, vi> inter;
    rep(i, 0, n) inter[X[i]].pb(hei[i]);
    set<int> posi;
    map<pii, vo<pii>> adj;
    repd(i, 0, m){
        auto [h, ind] = skys[i];
        
        while(shei.size() && shei.back().fi>=h){
            posi.insert(shei.back().se);
            shei.pop_back();
        }
        
        int pre = -1;
        auto it = posi.lower_bound(X[L[ind]]);
        while(it!=posi.end()){
            int x = *it;
            if(x > X[R[ind]]) break;
            if(pre!=-1) {
                adj[{x, h}].pb({pre, h});
                adj[{pre, h}].pb({x, h});
            }
            pre = x;
            inter[x].pb(h);
            it++;
        }
    }
    rep(i, 0, n) {inter[X[i]].pb(0); reverse(all(inter[X[i]]));}
    for(auto tmp: inter[9]) pr(tmp)

    // fix vertical edges
    rep(i, 0, n){
        int pre = -1;
        for(auto h: inter[X[i]]){
            if(pre!=-1){
                adj[{X[i], pre}].pb({X[i], h});
                adj[{X[i], h}].pb({X[i], pre});
            }
            pre = h;
        }
    }

    // dijkstra
    priority_queue<array<int, 3>, vo<array<int, 3>>, greater<array<int, 3>>> pq;
    pq.push({0, X[g], 0});
    map<pii, int> dist; dist[{X[g], 0}] = 0;
    while(pq.size()){
        auto [d, x, y] = pq.top(); pq.pop();
        if(pii{x, y} == pii{X[s], 0}) return d;

        for(auto [nx, ny]: adj[{x, y}]){
            int newd = d + abs(nx-x) + abs(ny - y);
            if(!dist.count({nx, ny}) || newd < dist[{nx, ny}]){
                dist[{nx, ny}] = newd;
                pq.push({newd, nx, ny});
            }
        }
    }

    return -1;
}

/*
subtask 1: bfs from goal
subtask 2: bfs from goal, 10*n nodes
subtask 3: choose lowest skywalk always
subtask 4: 

*/

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