oj.uz

Submission #703183

# Submission time Handle Problem Language Result Execution time Memory
703183 2023-02-26T13:26:39 Z qwerasdfzxcl Sky Walking (IOI19_walk) C++17
25 / 100
 1641 ms 115608 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
constexpr ll INF = 4e18;
constexpr int MAXN = 2002000;

int n, m;
vector<int> X, H, L, R, Y;
map<int, vector<pii>> Z;

struct Event{
    int l, r, y, typ;
    Event(){}
    Event(int _l, int _r, int _y, int _typ): l(_l), r(_r), y(_y), typ(_typ) {}
};

struct Graph{
    map<pii, int> V;
    vector<pii> adj[MAXN];
    ll dist[MAXN];
    int sz;

    int add_vertex(int x, int y){
        pii p(x, y);
        if (V[p]) return V[p];
        //printf(" add vertex: %d %d\n", x, y);
        V[p] = ++sz;

        assert(sz<MAXN);
        return sz;
    }

    void add_edge(int x1, int y1, int x2, int y2){
        //printf(" add edge: %d %d <-> %d %d\n", x1, y1, x2, y2);
        pii p1(x1, y1), p2(x2, y2);
        int i1 = add_vertex(x1, y1), i2 = add_vertex(x2, y2);
        int d = abs(x1-x2) + abs(y1-y2);

        adj[i1].emplace_back(i2, d);
        adj[i2].emplace_back(i1, d);
    }

    vector<pii> get_vertex(){
        vector<pii> ret;
        for (auto &[x, y]:V) ret.push_back(x);
        return ret;
    }

    ll calc(int s, int e){
        fill(dist+1, dist+sz+1, INF);
        dist[s] = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.emplace(dist[s], s);

        while(!pq.empty()){
            auto [d, cur] = pq.top(); pq.pop();
            if (d > dist[cur]) continue;
            assert(dist[cur] == d);
            for (auto &[nxt, e]:adj[cur]) if (dist[nxt] > dist[cur] + e){
                dist[nxt] = dist[cur] + e;
                pq.emplace(dist[nxt], nxt);
            }
        }

        return dist[e]==INF?-1:dist[e];
    }
}G;

int h(int x){
    int idx = lower_bound(X.begin(), X.end(), x) - X.begin();
    return H[idx];
}

void f(int x){
    //printf("\n f %d\n", x);
    vector<Event> E;
    for (int i=0;i<n;i++) E.emplace_back(X[i], X[i], H[i], 0);
    for (int i=0;i<m;i++) E.emplace_back(L[i], R[i], Y[i], -1);
    sort(E.begin(), E.end(), [&](const Event &a, const Event &b){return tie(a.y, a.typ) > tie(b.y, b.typ);});

    set<int> st;
    for (auto &[l, r, y, typ]:E){
        //printf("  %d %d %d %d\n", l, r, y, typ);
        if (typ==0) {st.insert(l); continue;}
        if (r<x || x<l) continue;

        auto iterL = st.upper_bound(x);
        auto iterR = st.lower_bound(x);
        if (iterL!=st.begin() && *prev(iterL) >= l) G.add_vertex(*--iterL, y);
        if (iterR!=st.end() && *iterR <= r) G.add_vertex(*iterR, y);
    }
}

void add_vertical(){
    //printf("\n vertical\n");
    auto V = G.get_vertex();
    vector<Event> E;
    multiset<pii> st;

    for (int i=0;i<m;i++){
        E.emplace_back(L[i], Y[i], i, 0);
        E.emplace_back(R[i], Y[i], i, 2);
    }
    for (auto &[x, y]:V) E.emplace_back(x, y, 0, 1);
    sort(E.begin(), E.end(), [&](const Event &a, const Event &b){return tie(a.l, a.typ) < tie(b.l, b.typ);});

    for (auto &[x, y, i, typ]:E){
        if (typ==0) st.emplace(y, i);
        else if (typ==2) st.erase(st.find(pii(y, i)));
        else{
            auto iter = st.lower_bound(pii(y, m+1));
            if (iter!=st.end() && iter->first <= h(x)) G.add_edge(x, y, x, iter->first);
        }
    }
}

void add_horizontal(){
    //printf("\n horizontal\n");
    auto V = G.get_vertex();
    sort(V.begin(), V.end(), [&](pii x, pii y){return tie(x.second, x.first) < tie(y.second, y.first);});

    for (int i=1;i<(int)V.size();i++) if (V[i-1].second == V[i].second){
        int x1 = V[i-1].first, x2 = V[i].first, y = V[i].second;

        auto iter = lower_bound(Z[y].begin(), Z[y].end(), pii(x2, -1));
        if (iter==Z[y].begin()) continue;
        --iter;

        if (iter->first <= x1 && x2 <= iter->second) G.add_edge(x1, y, x2, y);
    }
}

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 P1, int P2) {
	n = X.size(); m = L.size();
	P1 = X[P1], P2 = X[P2];
	for (auto &x:L) x = X[x];
	for (auto &x:R) x = X[x];

	::X = X, ::H = H, ::L = L, ::R = R, ::Y = Y;
	for (int i=0;i<m;i++){
        Z[Y[i]].emplace_back(L[i], R[i]);
	}
	for (auto iter=Z.begin();iter!=Z.end();iter++) sort(iter->second.begin(), iter->second.end());

	G.add_vertex(P1, 0);
	G.add_vertex(P2, 0);

    for (int i=0;i<m;i++){
        G.add_vertex(L[i], Y[i]);
        G.add_vertex(R[i], Y[i]);
    }

    f(P1); f(P2);
    add_vertical();
    add_horizontal();

    return G.calc(1, 2);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 27 ms 47312 KB Output is correct
3 Correct 26 ms 47244 KB Output is correct
4 Correct 24 ms 47220 KB Output is correct
5 Correct 24 ms 47328 KB Output is correct
6 Correct 25 ms 47320 KB Output is correct
7 Correct 25 ms 47256 KB Output is correct
8 Correct 26 ms 47316 KB Output is correct
9 Correct 27 ms 47316 KB Output is correct
10 Correct 25 ms 47236 KB Output is correct
11 Correct 25 ms 47300 KB Output is correct
12 Correct 25 ms 47240 KB Output is correct
13 Correct 25 ms 47268 KB Output is correct
14 Correct 24 ms 47316 KB Output is correct
15 Correct 23 ms 47220 KB Output is correct
16 Correct 25 ms 47316 KB Output is correct
17 Correct 24 ms 47316 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47272 KB Output is correct
2 Correct 24 ms 47212 KB Output is correct
3 Correct 962 ms 104620 KB Output is correct
4 Incorrect 885 ms 103684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 59412 KB Output is correct
2 Correct 994 ms 112016 KB Output is correct
3 Correct 1272 ms 113272 KB Output is correct
4 Correct 1366 ms 115608 KB Output is correct
5 Correct 1336 ms 113744 KB Output is correct
6 Correct 1368 ms 111660 KB Output is correct
7 Correct 553 ms 84220 KB Output is correct
8 Correct 613 ms 93724 KB Output is correct
9 Correct 1219 ms 109084 KB Output is correct
10 Correct 655 ms 93584 KB Output is correct
11 Correct 58 ms 51824 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 59412 KB Output is correct
2 Correct 994 ms 112016 KB Output is correct
3 Correct 1272 ms 113272 KB Output is correct
4 Correct 1366 ms 115608 KB Output is correct
5 Correct 1336 ms 113744 KB Output is correct
6 Correct 1368 ms 111660 KB Output is correct
7 Correct 553 ms 84220 KB Output is correct
8 Correct 613 ms 93724 KB Output is correct
9 Correct 1219 ms 109084 KB Output is correct
10 Correct 655 ms 93584 KB Output is correct
11 Correct 58 ms 51824 KB Output is correct
12 Correct 1334 ms 113096 KB Output is correct
13 Correct 1299 ms 115448 KB Output is correct
14 Correct 1641 ms 113672 KB Output is correct
15 Correct 908 ms 97120 KB Output is correct
16 Correct 911 ms 101892 KB Output is correct
17 Correct 966 ms 109204 KB Output is correct
18 Correct 800 ms 97192 KB Output is correct
19 Correct 880 ms 101852 KB Output is correct
20 Correct 581 ms 82824 KB Output is correct
21 Correct 118 ms 56176 KB Output is correct
22 Correct 773 ms 98552 KB Output is correct
23 Correct 722 ms 96884 KB Output is correct
24 Correct 594 ms 90576 KB Output is correct
25 Correct 691 ms 96364 KB Output is correct
26 Correct 571 ms 91984 KB Output is correct
27 Correct 1291 ms 113784 KB Output is correct
28 Correct 1038 ms 115088 KB Output is correct
29 Correct 1249 ms 111744 KB Output is correct
30 Correct 550 ms 83936 KB Output is correct
31 Correct 1181 ms 109096 KB Output is correct
32 Correct 544 ms 85292 KB Output is correct
33 Incorrect 548 ms 85612 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 27 ms 47312 KB Output is correct
3 Correct 26 ms 47244 KB Output is correct
4 Correct 24 ms 47220 KB Output is correct
5 Correct 24 ms 47328 KB Output is correct
6 Correct 25 ms 47320 KB Output is correct
7 Correct 25 ms 47256 KB Output is correct
8 Correct 26 ms 47316 KB Output is correct
9 Correct 27 ms 47316 KB Output is correct
10 Correct 25 ms 47236 KB Output is correct
11 Correct 25 ms 47300 KB Output is correct
12 Correct 25 ms 47240 KB Output is correct
13 Correct 25 ms 47268 KB Output is correct
14 Correct 24 ms 47316 KB Output is correct
15 Correct 23 ms 47220 KB Output is correct
16 Correct 25 ms 47316 KB Output is correct
17 Correct 24 ms 47316 KB Output is correct
18 Correct 27 ms 47272 KB Output is correct
19 Correct 24 ms 47212 KB Output is correct
20 Correct 962 ms 104620 KB Output is correct
21 Incorrect 885 ms 103684 KB Output isn't correct
22 Halted 0 ms 0 KB -