Submission #778558

#	Time	Username	Problem	Language	Result	Execution time	Memory
778558		jasmin	Sky Walking (IOI19_walk)	C++17	24 / 100	4074 ms	502832 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, unordered_map<int, unordered_map<int, vector<pair<int,int> > > >& adi, int a, int b, vector<int>& x){

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

    unordered_map<int, unordered_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();

    //compressing skywalks
    /*map<int, vector<pair<int,int> > > sw;
    for(int i=0; i<m; i++){
        sw[ yinit[i] ].push_back({linit[i], rinit[i]});
    }

    vector<int> l;
    vector<int> r;
    vector<int> y;
    for(auto [hi, vec]: sw){

        pair<int,int> last={-1, -1};
        for(auto [left, right]: vec){

            if(last.second==left){
                last.second=right;
            }
            else{
                l.push_back(last.first);
                r.push_back(last.second);
                y.push_back(hi);

                last={left, right};
            }

        }

        l.push_back(last.first);
        r.push_back(last.second);
        y.push_back(hi);
    }
    m=l.size();*/


    //build graph

    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;
    unordered_map<int, unordered_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({x[l[i]], 0});
        while(next(p)!=active.end() && (*next(p)).first<=x[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);
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    vector<int> h(n);
    for(int i=0; i<n; i++){
        cin >> x[i];
    }
    for(int i=0; i<n; i++){
        cin >> h[i];
    }

    vector<int> l(m);
    vector<int> r(m);
    vector<int> y(m);
    for(int i=0; i<m; i++){
        cin >> l[i];
    }
    for(int i=0; i<m; i++){
        cin >> r[i];
    }
    for(int i=0; i<m; i++){
        cin >> y[i];
    }

    int s, g;
    cin >> s >> g;

    cout << min_distance(x, h, l, r, y, s, g) << "\n";
}*/

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