oj.uz

Submission #1026641

# Submission time Handle Problem Language Result Execution time Memory
1026641 2024-07-18T08:57:57 Z hotboy2703 Sky Walking (IOI19_walk) C++17
15 / 100
 649 ms 152644 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*20];
ll dist[MAXN*20];
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];
}
ll SUSSYBAKA;
struct point{
    ll x,y,id;
    point(ll x1=-1,ll y1=-1):x(x1),y(y1),id(x1==-1?-1:SUSSYBAKA++){
    }
    bool operator < (const point &p)const {
        return MP(x,y)<MP(p.x,p.y);
    }
    bool operator == (const point &p)const {
        return MP(x,y)==MP(p.x,p.y);
    }
};
vector <point> vertices;
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;
    vertices.emplace_back(X[S],0);
    vertices.emplace_back(X[G],0);
    for (auto x:all){
        vertices.emplace_back(X[x.l],x.y);
        vertices.emplace_back(X[x.r],x.y);
    }
    auto add_vertex = [&](bool inv){
        vector <ll> bd;
        for (ll i = inv?n:0;inv?i>=0:i<n;inv?i--:i++){
            if (sz(bd) && h[bd.back()] < h[i])bd.pop_back();
            bd.push_back(i);
            if (i==S||i==G){
                ll ptr = sz(bd)-1;
                for (auto x:all){
                    while (ptr>=0&&h[bd[ptr]] < x.y)ptr--;
                    if (x.l <= ptr && ptr <= x.r){
                        vertices.emplace_back(X[bd[ptr]],all[i].y);
                    }
                }
            }
        }
    };
    add_vertex(0);
    add_vertex(1);
    vector <pair <pll,bool> > event;
    for (auto x:all){
        event.emplace_back(MP(X[x.l],x.y),1);
        event.emplace_back(MP(X[x.r]+1,x.y),0);
    }
    sort(event.begin(),event.end());
    sort(vertices.begin(),vertices.end());
    vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());
//    return -1;
    {
        ll ptr = 0;
        multiset <ll> ms;
        vector <pll> Tm;
        for (auto x:vertices){
            while (ptr<sz(event) && event[ptr].fi.fi <= x.x){
                if (event[ptr].se)ms.insert(event[ptr].fi.se);
                else ms.erase(ms.find((event[ptr].fi.se)));
                ptr++;
            }
//            cout<<x.x<<' '<<x.y<<endl;
            auto tmp = ms.upper_bound(x.y);
            if (tmp != ms.end()){
//                    cout<<SUSSYBAKA<<endl;cout<<"BRUH "<<(*tmp)<<endl;
                Tm.emplace_back(x.x,*(tmp));
            }
            tmp = ms.lower_bound(x.y);
            if (tmp != ms.begin())Tm.emplace_back(x.x,*prev(tmp));
        }
        for (auto x:Tm)vertices.emplace_back(x.fi,x.se);
    }
//    return -1;
    sort(vertices.begin(),vertices.end());
    vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());
    auto add_edge = [&](point a1,point a2){
        ll w = abs(a1.x-a2.x) + abs(a1.y-a2.y);
//        cout<<a1.x<<' '<<a1.y<<' '<<a2.x<<' '<<a2.y<<'\n';
//        assert(a1.id < MAXN*40);
        g[a1.id].push_back(MP(a2.id,w));
        g[a2.id].push_back(MP(a1.id,w));
    };
    for (ll j = 0;j + 1 < sz(vertices);j ++){
        if (vertices[j].x == vertices[j+1].x)add_edge(vertices[j],vertices[j+1]);
    }
    auto cmp_y = [](point a1,point a2){return MP(a1.y,a1.x) < MP(a2.y,a2.x);};
    sort(vertices.begin(),vertices.end(),cmp_y);
    auto fi = [&](pll x){
        return lower_bound(vertices.begin(),vertices.end(),x,
                           [](point a1,pll val){return MP(a1.y,a1.x) < MP(val.se,val.fi);})-vertices.begin();
    };
    vector <ll> cnt(sz(vertices));
    for (auto x:all){
        cnt[fi(MP(X[x.l],x.y))] ++;
        cnt[fi(MP(X[x.r],x.y))] --;
    }
    for (ll i = 0;i < sz(vertices);i ++){
        if (i)cnt[i]+=cnt[i-1];
        if (cnt[i]){
            add_edge(vertices[i],vertices[i+1]);
        }
    }
//    for (auto x:vertices)cout<<"SUS "<<x.x<<' '<<x.y<<' '<<x.id<<endl;
    for (ll i = 0;i < sz(vertices);i ++){
        if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[S]),0LL))S = vertices[i].id;
        if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[G]),0LL))G = vertices[i].id;

    }
    return dijkstra(S,G);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 76256 KB Output is correct
2 Correct 490 ms 138180 KB Output is correct
3 Correct 497 ms 144424 KB Output is correct
4 Correct 569 ms 150820 KB Output is correct
5 Correct 649 ms 151348 KB Output is correct
6 Correct 569 ms 146864 KB Output is correct
7 Correct 266 ms 110268 KB Output is correct
8 Correct 234 ms 101736 KB Output is correct
9 Correct 496 ms 141268 KB Output is correct
10 Correct 234 ms 118320 KB Output is correct
11 Correct 18 ms 65092 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 76256 KB Output is correct
2 Correct 490 ms 138180 KB Output is correct
3 Correct 497 ms 144424 KB Output is correct
4 Correct 569 ms 150820 KB Output is correct
5 Correct 649 ms 151348 KB Output is correct
6 Correct 569 ms 146864 KB Output is correct
7 Correct 266 ms 110268 KB Output is correct
8 Correct 234 ms 101736 KB Output is correct
9 Correct 496 ms 141268 KB Output is correct
10 Correct 234 ms 118320 KB Output is correct
11 Correct 18 ms 65092 KB Output is correct
12 Correct 502 ms 143356 KB Output is correct
13 Correct 424 ms 149660 KB Output is correct
14 Correct 620 ms 152644 KB Output is correct
15 Correct 432 ms 133472 KB Output is correct
16 Correct 475 ms 139840 KB Output is correct
17 Correct 539 ms 149568 KB Output is correct
18 Correct 432 ms 132188 KB Output is correct
19 Correct 476 ms 136992 KB Output is correct
20 Correct 271 ms 108392 KB Output is correct
21 Runtime error 65 ms 106100 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -