Submission #1077120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077120		HD1	Sky Walking (IOI19_walk)	C++14	10 / 100	1331 ms	347844 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(x) ll(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6+10;
const ll inf=1e18;
vector<ii>gfo[MAX];
ll cur[MAX], dist[MAX];
void dikstra(ll ini){
    set<ii> q;
    q.insert({0,ini});
    dist[ini]=0;
    while(sz(q)){
        auto x=*q.begin();
        q.erase(q.begin());
        ll u=x.ss;
        ll dist_u=x.ff;
        if(dist_u!=dist[u])continue;
        for(auto y:gfo[u]){
            ll w=y.ss;
            ll v=y.ff;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                q.insert({dist[v], v});
            }
        }
    }
}
map< pair<ll,ll>, ll> M;
set<ll> torre;
long long min_distance(vector<int> x,vector<int> h,
    vector<int> l,vector<int> r, 
    vector<int> y, int s, int g) {
    vector<pair<int,ii>> c;
    ll m=sz(y);//numero de rascacielos
    ll n=sz(x);//numero de torres
    for(ll i=0; i<m; i++){
        c.pb({y[i],{l[i],r[i]}});// por su altura
    }
    for(ll i=0; i<n; i++){
        torre.insert(i);
    }
    torre.insert(inf);
    sort(all(c));
    ll nod=0, nod_prev=0, mx=0, pos=0;
    for(ll i=0; i<n; i++){
        if(!M.count({x[i], 0})){
            M[{x[i],0}]=mx+1;
            mx++;
            cur[i]=0;//altura
        }
    }
    //cout<<mx<<'\n';
    for(auto q:c){//rascacielo en la altura q.ff
        ll alt=q.ff;
        ll l=q.ss.ff, r=q.ss.ss;
        //cout<<l<<' '<<r<<'\n';
        vector<ll>ers;
        for(auto it=torre.lower_bound(l); it!=torre.end() && it!=torre.upper_bound(r); it++){
            //cout<<*it<<'\n';
            //cout<<alt<<' '<<h[*it]<<' '<<*it<<'\n';
            if(alt<=h[*it]){// hay interseccion
                //cout<<"quepasa"<<'\n';
                if(!M.count({x[*it],alt})){//creamos el nodo
                    M[{x[*it],alt}]=mx+1;
                    mx++;
                }
                //cout<<"normal "<<*it<<'\n';
                nod=M[{x[*it],alt}];
                // vertical
                gfo[nod].pb({M[{x[*it], cur[*it]}],alt-cur[*it]});
                gfo[M[{x[*it], cur[*it]}]].pb({nod,alt-cur[*it]});
                cur[*it]=alt;
                if(*it==l){
                    nod_prev=nod;
                    pos=x[*it];
                    continue;
                }
                //horizontal
                //cout<<"normal2 "<<*it<<'\n';
                gfo[nod].pb({nod_prev, x[*it]-pos});
                gfo[nod_prev].pb({nod, x[*it]-pos});
                nod_prev=nod;
                pos=x[*it];
            }
            else {
                ers.pb(*it);
            }
        }
        for(ll w:ers){
            torre.erase(torre.find(w));
        }
    }
    // cout<<"muereeeeee"<<'\n';
    // for(auto a:M){
    //  cout<<a.ff.ff<<' '<<a.ff.ss<<" -> "<<a.ss<<'\n';
    // }
    // for(auto a:M){
    //  cout<<a.ss<<" -> ";
    //  for(auto b:gfo[a.ss]){
    //      cout<<b.ff<<", "<<b.ss;
    //      cout<<'\n';
    //  }
    //  cout<<'\n';
    // }
    for(ll i=0; i<=mx; i++)dist[i]=inf;
    dikstra(M[{x[s],0}]);
    ll ans=dist[M[{x[g],0}]];
    if(ans==inf)ans=-1;
    return ans;
}

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