Submission #992356

#	Time	Username	Problem	Language	Result	Execution time	Memory
992356		MarwenElarbi	Sky Walking (IOI19_walk)	C++17	10 / 100	651 ms	325220 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e6;
vector<pair<int,int>> adj[nax];
vector<long long> dis(nax);
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    int n=x.size();
    int k=l.size();
    int cnt=n;
    vector<pair<int,pair<int,int>>> tab(k);
    for (int i = 0; i < k; ++i)
    {
        tab[i]={y[i],{l[i],r[i]}};
    }
    sort(tab.begin(),tab.end());
    map<int,pair<int,int>> mp;
    for (int i = 0; i < n; ++i)
    {
        mp[x[i]]={i,0};
    }
    for (int i = 0; i < k; ++i)
    {
        for (int j = tab[i].se.fi; j <= tab[i].se.se; ++j)
        {
            if(tab[i].fi<=h[j]){
                adj[cnt].pb({mp[x[j]].fi,tab[i].fi-mp[x[j]].se});
                adj[mp[x[j]].fi].pb({cnt,tab[i].fi-mp[x[j]].se});
                mp[x[j]]={cnt,tab[i].fi};
            }
            if(j>tab[i].se.fi){
                adj[cnt].pb({cnt-1,x[j]-x[j-1]});
                adj[cnt-1].pb({cnt,x[j]-x[j-1]});
            }
            cnt++;
        }
    }
    for (int i = 0; i < cnt; ++i)
    {
        dis[i]=1e18;
    }
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    pq.push({0,s});
    dis[s]=0;
    //cout <<"hey"<<endl;
    //int t=5;
    while(!pq.empty()){
        //cout <<t<<endl;
        //if(t==0) break;
        //t--;
        ll d=pq.top().fi;
        ll x=pq.top().se;
        //cout <<x<<" "<<d<<endl;
        pq.pop();
        if(x==g){
            return d;
        }
        if(dis[x]!=d) continue;
        for(auto u:adj[x]){
            //cout <<"n "<<u.fi<<endl;
            ll newd=u.se+d;
            //cout <<u.se<<endl;
            if(newd>=dis[u.fi]) continue;
            dis[u.fi]=newd;
            pq.push({newd,u.fi});
        }
    }
    return -1;
}

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