oj.uz

Submission #703179

# Submission time Handle Problem Language Result Execution time Memory
703179 2023-02-26T12:54:52 Z qwerasdfzxcl Sky Walking (IOI19_walk) C++17
33 / 100
 1725 ms 148576 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, i));
            if (y==0){
                if (iter!=st.end() && iter->first <= h(x)) G.add_edge(x, y, x, iter->first);
                continue;
            }
            assert(iter!=st.end());

            if (iter!=st.begin()) G.add_edge(x, y, x, prev(iter)->first);
            if (next(iter)!=st.end() && next(iter)->first <= h(x)) G.add_edge(x, y, x, next(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, y));
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 27 ms 47212 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 24 ms 47228 KB Output is correct
5 Correct 24 ms 47244 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 23 ms 47268 KB Output is correct
8 Correct 24 ms 47284 KB Output is correct
9 Correct 24 ms 47316 KB Output is correct
10 Correct 25 ms 47360 KB Output is correct
11 Correct 38 ms 47304 KB Output is correct
12 Incorrect 25 ms 47316 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47288 KB Output is correct
2 Correct 25 ms 47312 KB Output is correct
3 Correct 1249 ms 119888 KB Output is correct
4 Correct 1092 ms 122268 KB Output is correct
5 Correct 711 ms 104856 KB Output is correct
6 Correct 675 ms 100496 KB Output is correct
7 Correct 732 ms 105132 KB Output is correct
8 Correct 1365 ms 125384 KB Output is correct
9 Correct 980 ms 117088 KB Output is correct
10 Incorrect 1147 ms 125804 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 58700 KB Output is correct
2 Correct 1361 ms 142224 KB Output is correct
3 Correct 1642 ms 145996 KB Output is correct
4 Correct 1593 ms 148576 KB Output is correct
5 Correct 1725 ms 147272 KB Output is correct
6 Correct 1565 ms 141884 KB Output is correct
7 Correct 693 ms 99956 KB Output is correct
8 Correct 590 ms 90796 KB Output is correct
9 Correct 1457 ms 135420 KB Output is correct
10 Correct 622 ms 96352 KB Output is correct
11 Correct 33 ms 48464 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 58700 KB Output is correct
2 Correct 1361 ms 142224 KB Output is correct
3 Correct 1642 ms 145996 KB Output is correct
4 Correct 1593 ms 148576 KB Output is correct
5 Correct 1725 ms 147272 KB Output is correct
6 Correct 1565 ms 141884 KB Output is correct
7 Correct 693 ms 99956 KB Output is correct
8 Correct 590 ms 90796 KB Output is correct
9 Correct 1457 ms 135420 KB Output is correct
10 Correct 622 ms 96352 KB Output is correct
11 Correct 33 ms 48464 KB Output is correct
12 Correct 1654 ms 145764 KB Output is correct
13 Correct 1481 ms 148452 KB Output is correct
14 Correct 1695 ms 147376 KB Output is correct
15 Correct 1062 ms 120828 KB Output is correct
16 Correct 1053 ms 121036 KB Output is correct
17 Correct 1266 ms 141128 KB Output is correct
18 Correct 1018 ms 120784 KB Output is correct
19 Correct 1087 ms 120996 KB Output is correct
20 Correct 715 ms 98544 KB Output is correct
21 Correct 51 ms 50636 KB Output is correct
22 Correct 995 ms 123528 KB Output is correct
23 Correct 905 ms 117700 KB Output is correct
24 Correct 643 ms 96528 KB Output is correct
25 Correct 866 ms 113612 KB Output is correct
26 Correct 507 ms 87112 KB Output is correct
27 Correct 1705 ms 147328 KB Output is correct
28 Correct 1478 ms 147124 KB Output is correct
29 Correct 1696 ms 141756 KB Output is correct
30 Correct 688 ms 99632 KB Output is correct
31 Correct 1427 ms 135516 KB Output is correct
32 Correct 567 ms 88252 KB Output is correct
33 Correct 556 ms 87576 KB Output is correct
34 Correct 655 ms 92696 KB Output is correct
35 Correct 705 ms 97128 KB Output is correct
36 Correct 607 ms 87844 KB Output is correct
37 Correct 462 ms 81348 KB Output is correct
38 Correct 435 ms 80608 KB Output is correct
39 Correct 664 ms 93104 KB Output is correct
40 Correct 539 ms 81704 KB Output is correct
41 Correct 512 ms 81084 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 27 ms 47212 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 24 ms 47228 KB Output is correct
5 Correct 24 ms 47244 KB Output is correct
6 Correct 24 ms 47316 KB Output is correct
7 Correct 23 ms 47268 KB Output is correct
8 Correct 24 ms 47284 KB Output is correct
9 Correct 24 ms 47316 KB Output is correct
10 Correct 25 ms 47360 KB Output is correct
11 Correct 38 ms 47304 KB Output is correct
12 Incorrect 25 ms 47316 KB Output isn't correct
13 Halted 0 ms 0 KB -