oj.uz

Submission #703181

# Submission time Handle Problem Language Result Execution time Memory
703181 2023-02-26T13:24:11 Z qwerasdfzxcl Sky Walking (IOI19_walk) C++17
10 / 100
 700 ms 90000 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, n+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 23 ms 47276 KB Output is correct
2 Correct 29 ms 47240 KB Output is correct
3 Correct 25 ms 47308 KB Output is correct
4 Correct 24 ms 47264 KB Output is correct
5 Correct 25 ms 47360 KB Output is correct
6 Correct 24 ms 47308 KB Output is correct
7 Correct 24 ms 47264 KB Output is correct
8 Correct 27 ms 47252 KB Output is correct
9 Correct 24 ms 47308 KB Output is correct
10 Correct 24 ms 47316 KB Output is correct
11 Correct 24 ms 47316 KB Output is correct
12 Correct 25 ms 47340 KB Output is correct
13 Correct 25 ms 47328 KB Output is correct
14 Correct 25 ms 47276 KB Output is correct
15 Correct 27 ms 47328 KB Output is correct
16 Correct 24 ms 47316 KB Output is correct
17 Correct 26 ms 47316 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47212 KB Output is correct
2 Correct 23 ms 47308 KB Output is correct
3 Incorrect 700 ms 90000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 59396 KB Output is correct
2 Incorrect 634 ms 88732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 59396 KB Output is correct
2 Incorrect 634 ms 88732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47276 KB Output is correct
2 Correct 29 ms 47240 KB Output is correct
3 Correct 25 ms 47308 KB Output is correct
4 Correct 24 ms 47264 KB Output is correct
5 Correct 25 ms 47360 KB Output is correct
6 Correct 24 ms 47308 KB Output is correct
7 Correct 24 ms 47264 KB Output is correct
8 Correct 27 ms 47252 KB Output is correct
9 Correct 24 ms 47308 KB Output is correct
10 Correct 24 ms 47316 KB Output is correct
11 Correct 24 ms 47316 KB Output is correct
12 Correct 25 ms 47340 KB Output is correct
13 Correct 25 ms 47328 KB Output is correct
14 Correct 25 ms 47276 KB Output is correct
15 Correct 27 ms 47328 KB Output is correct
16 Correct 24 ms 47316 KB Output is correct
17 Correct 26 ms 47316 KB Output is correct
18 Correct 24 ms 47212 KB Output is correct
19 Correct 23 ms 47308 KB Output is correct
20 Incorrect 700 ms 90000 KB Output isn't correct
21 Halted 0 ms 0 KB -