Submission #1025999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025999		hotboy2703	Sky Walking (IOI19_walk)	C++17	0 / 100	4086 ms	48044 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
struct walk{
    ll l,r,y;
};
vector <walk> all;
const ll MAXN = 1e5 + 100;
const ll INF = 1e18;
vector <pll> g[MAXN*10];
ll dist[MAXN*10];
ll dijkstra(ll s,ll t){
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;
    priority_queue <pll,vector <pll> ,greater <> > q;
    q.push(MP(dist[s],s));
    while (!q.empty()){
        auto u = q.top().se;
        ll val = q.top().fi;
        q.pop();
        if (dist[u] != val)continue;
        for (auto tmp:g[u]){
            ll v = tmp.fi,w = tmp.se;
            if (dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                q.push(MP(dist[v],v));
            }
        }
    }
    if (dist[t] >=INF)dist[t] = -1;
    return dist[t];
}
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){
    ll m = sz(l);
    ll n = sz(x);
    for (ll i = 0;i < m;i ++){
        all.push_back({l[i],r[i],y[i]});
    }
    sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.y>a2.y;});
    vector <ll> order;
    order.resize(n);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](ll x,ll y){return h[x] > h[y];});
//    cout<<"OK"<<endl;
    vector <pll> vertices;
    S=x[S],G=x[G];
    vertices.push_back(MP(S,0));
    vertices.push_back(MP(G,0));
    {
        set <ll> s;
        s.insert(-1);
        s.insert(n);
        for (ll i = 0,ptr = 0;i < m;i ++){
            while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
                s.insert(order[ptr]);
                ptr++;
            }
            vector <ll> tmp;
            for (auto it = lower_bound(s.begin(),s.end(),all[i].l);*it <= all[i].r;it ++){
                tmp.push_back(x[*it]);
            }
            assert(sz(tmp) <= 10);
            for (auto x:tmp)vertices.push_back(MP(x,all[i].y));
        }
    }

    sort(vertices.begin(),vertices.end());
//    for (auto x:vertices){
//        cout<<x.fi<<' '<<x.se<<endl;
//    }
    auto get_id = [&](pll x){
        return lower_bound(vertices.begin(),vertices.end(),x)-vertices.begin();
    };
    auto add_edge = [&](pll x,pll y){
        ll x1 = get_id(x);
        ll y1 = get_id(y);
        ll w = abs(x.fi-y.fi)+abs(x.se-y.se);
        g[x1].push_back(MP(y1,w));
        g[y1].push_back(MP(x1,w));
    };
    {
        set <ll> s;
        s.insert(-1);
        s.insert(n);
        for (ll i = 0,ptr = 0;i < m;i ++){
            while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
                s.insert(order[ptr]);
                ptr++;
            }
            vector <ll> tmp;
            for (auto it = lower_bound(s.begin(),s.end(),all[i].l);*it <= all[i].r;it ++){
                tmp.push_back(x[*it]);
            }
            for (ll j = 0;j + 1 < sz(tmp);j ++){
                add_edge(MP(tmp[j],all[i].y),MP(tmp[j+1],all[i].y));
            }
        }
    }
    for (ll i = 0;i + 1 < sz(vertices);i ++){
        if (vertices[i].fi == vertices[i+1].fi)add_edge(vertices[i],vertices[i+1]);
    }
    return dijkstra(get_id(MP(S,0)),get_id(MP(G,0)));
}

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