oj.uz

답안 #1026817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026817 2024-07-18T12:00:49 Z hotboy2703 Sky Walking (IOI19_walk) C++17
15 / 100
 652 ms 153436 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-1:0;inv?i>=0:i<n;inv?i--:i++){
//            cout<<i<<endl;
            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++;
            }
            auto tmp = ms.upper_bound(x.y);
            if (tmp != ms.end())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);
    }
    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);
        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]){
//            assert(i != sz(vertices)-1);
            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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 76296 KB Output is correct
2 Correct 444 ms 137932 KB Output is correct
3 Correct 498 ms 142604 KB Output is correct
4 Correct 628 ms 148968 KB Output is correct
5 Correct 652 ms 152856 KB Output is correct
6 Correct 547 ms 148276 KB Output is correct
7 Correct 277 ms 109956 KB Output is correct
8 Correct 223 ms 100116 KB Output is correct
9 Correct 519 ms 141772 KB Output is correct
10 Correct 233 ms 116652 KB Output is correct
11 Correct 19 ms 65092 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 76296 KB Output is correct
2 Correct 444 ms 137932 KB Output is correct
3 Correct 498 ms 142604 KB Output is correct
4 Correct 628 ms 148968 KB Output is correct
5 Correct 652 ms 152856 KB Output is correct
6 Correct 547 ms 148276 KB Output is correct
7 Correct 277 ms 109956 KB Output is correct
8 Correct 223 ms 100116 KB Output is correct
9 Correct 519 ms 141772 KB Output is correct
10 Correct 233 ms 116652 KB Output is correct
11 Correct 19 ms 65092 KB Output is correct
12 Correct 504 ms 143376 KB Output is correct
13 Correct 453 ms 149260 KB Output is correct
14 Correct 624 ms 153436 KB Output is correct
15 Correct 489 ms 130256 KB Output is correct
16 Correct 454 ms 138272 KB Output is correct
17 Correct 528 ms 149900 KB Output is correct
18 Correct 440 ms 129972 KB Output is correct
19 Correct 444 ms 136972 KB Output is correct
20 Correct 293 ms 109580 KB Output is correct
21 Runtime error 64 ms 106100 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -