Submission #778531

#	Time	Username	Problem	Language	Result	Execution time	Memory
778531		jasmin	Sky Walking (IOI19_walk)	C++17	0 / 100	15 ms	3136 KiB

walk

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

const long long INF=1e18;

int distance(int i, int h, int j, int h2, vector<int>& x){
    return abs(x[i]-x[j]) + abs(h-h2);
}

long long dijkstra(int n, map<int, map<int, vector<pair<int,int> > > >& adi, int a, int b, vector<int>& x){

    map<int, map<int, long long> > dist; //plus 1
    dist[a][0]=1;

    map<int, map<int, bool> > vis;

    priority_queue<pair<long long, pair<int,int> > > pq;
    pq.push({-1, {a, 0}});
    while(!pq.empty()){
        auto [v, h] = pq.top().second;
        pq.pop();

        if(vis[v][h]) continue;
        vis[v][h]=true;

        for(auto [u, h2]: adi[v][h]){

            if(dist[u][h2]==0 || dist[v][h]+distance(v, h, u, h2, x)<dist[u][h2]){

                dist[u][h2] = dist[v][h] + distance(v, h, u, h2, x);
                pq.push({-dist[u][h2], {u, h2}});
            }
        }

    }

    return dist[b][0]-1;
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	
    int n=x.size();
    int m=l.size();

    vector<int> sorth(n, 0);
    iota(sorth.begin(), sorth.end(), 0);
    sort(sorth.begin(), sorth.end(), [&](int i, int j){
        return h[i]<h[j];
    });

    vector<int> sorty(m, 0);
    iota(sorty.begin(), sorty.end(), 0);
    sort(sorty.begin(), sorty.end(), [&](int i, int j){
        return y[i]<y[j];
    });

    set<pair<int, int> > active;
    for(int i=0; i<n; i++){
        active.insert({x[i], i});
    }

    int j=0;
    map<int, map<int, vector<pair<int,int> > > > adi;
    vector<set<int> > hights(n, {0});

    for(auto i: sorty){
        while(j<n && h[sorth[j]] < y[i]){
            active.erase({x[sorth[j]], sorth[j]});
            j++;
        }

        auto p = active.lower_bound({l[i], 0});
        while(next(p)!=active.end() && (*next(p)).first<=r[i]){

            //horizontal conection

            int ind=(*p).second;
            int ind2=(*next(p)).second;

            adi[ind][y[i]].push_back({ind2, y[i]}); hights[ind].insert(y[i]);
            adi[ind2][y[i]].push_back({ind, y[i]}); hights[ind2].insert(y[i]);

            p=next(p);
        }
    }

    for(int i=0; i<n; i++){
        int last=*hights[i].begin();

        for(auto e: hights[i]){
            if(e==last) continue;

            adi[i][last].push_back({i, e});
            adi[i][e].push_back({i, last});

            last=e;
        }
    }

    return dijkstra(n, adi, s, g, x);
}

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