oj.uz

Submission #1026015

# Submission time Handle Problem Language Result Execution time Memory
1026015 2024-07-17T12:37:14 Z hotboy2703 Sky Walking (IOI19_walk) C++17
14 / 100
 1085 ms 139236 KB 
#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));
//    return -1;
    {
        set <ll> s;
        s.insert(-1);
        s.insert(n);
        for (ll i = 0,ptr = 0;i < m;i ++){
//            cout<<i<<'\n';
//            if (i % 1000==0)cout<<i<<endl;
            while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
                s.insert(order[ptr]);
                ptr++;
            }

            vector <ll> tmp;
            for (auto it = s.lower_bound(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));
        }
    }
//    if (n==100000)return -1;
    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 = s.lower_bound(all[i].l);*it <= all[i].r;it ++){
                tmp.push_back(x[*it]);
            }
//            cout<<sz(tmp)<<'\n';
            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.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31632 KB Output is correct
4 Runtime error 24 ms 48220 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 693 ms 107272 KB Output is correct
4 Correct 742 ms 110156 KB Output is correct
5 Correct 499 ms 98652 KB Output is correct
6 Correct 422 ms 91060 KB Output is correct
7 Correct 477 ms 98656 KB Output is correct
8 Correct 889 ms 126440 KB Output is correct
9 Correct 562 ms 99860 KB Output is correct
10 Correct 1085 ms 139236 KB Output is correct
11 Correct 438 ms 74148 KB Output is correct
12 Correct 273 ms 57240 KB Output is correct
13 Correct 883 ms 125984 KB Output is correct
14 Correct 194 ms 55996 KB Output is correct
15 Correct 195 ms 56516 KB Output is correct
16 Correct 217 ms 58060 KB Output is correct
17 Correct 216 ms 57104 KB Output is correct
18 Correct 126 ms 63748 KB Output is correct
19 Correct 18 ms 32924 KB Output is correct
20 Correct 93 ms 43780 KB Output is correct
21 Correct 210 ms 57028 KB Output is correct
22 Correct 207 ms 56260 KB Output is correct
23 Correct 211 ms 63676 KB Output is correct
24 Correct 195 ms 57164 KB Output is correct
25 Correct 223 ms 57276 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 44996 KB Output is correct
2 Runtime error 52 ms 59844 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 44996 KB Output is correct
2 Runtime error 52 ms 59844 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31632 KB Output is correct
4 Runtime error 24 ms 48220 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -