oj.uz

Submission #725919

# Submission time Handle Problem Language Result Execution time Memory
725919 2023-04-18T08:50:07 Z PixelCat Sky Walking (IOI19_walk) C++14
24 / 100
 2029 ms 678540 KB 
#include "walk.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i,a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
using Vi = vector<int32_t>;

const int MAXN = 100010;
const int INF = 2e9;

int n, m;

Vi st[MAXN], ed[MAXN];
int solve_1n(Vi x, Vi h, Vi l, Vi r, Vi y) {
    For(i, 0, m - 1) {
        st[l[i]].eb(y[i]);
        ed[r[i]].eb(y[i]);
    }
    map<int, int> mp;
    mp[0] = INF; mp[INF] = INF;
    for(auto &i:st[0]) mp[i] = i;
    auto eval = [&](int p, int hei) {
        auto it1 = mp.upper_bound(p);
        auto it2 = prev(it1);
        int res = p - (it2->F) + (it2->S);
        if(it1->F <= hei) {
            res = min(res, (it1->F) - p + (it1->S));
        }
        // cout << (it1->F) << " " << (it1->S) << "\n";
        // cout << (it2->F) << " " << (it2->S) << "\n";
        return res;
    };
    For(i, 1, n - 2) {
        set<int> upd;
        for(auto &j:st[i]) {
            int k = eval(j, h[i]);
            mp[j] = k;
            upd.insert(j);
        }
        for(auto &j:ed[i]) if(!upd.count(j)) {
            mp.erase(j);
        }
    }
    // cout << "\n";
    // for(auto &p:mp) cout << p.F << " " << p.S << "\n";
    // cout << "\n";
    int ans = eval(0, h[n - 1]) + x.back() - x[0];
    if(ans >= INF) return -1;
    return ans;
}

const int MAXND = 2000010;
int nd_count = 0;
vector<pii> adj[MAXND];
int dist[MAXND];
int solve(Vi x, Vi h, Vi l, Vi r, Vi Y, int s, int g) {
    For(i, 0, m - 1) {
        st[l[i]].eb(Y[i]);
        ed[r[i]].eb(Y[i]);
    }
    map<int, pii> mp; // {y, {x, id}}
    map<pii, int> nodes;
    auto new_node = [&](int x1, int y1) {
        auto p = pii(x1, y1);
        if(nodes.count(p)) return nodes[p];
        nd_count++;
        nodes[p] = nd_count;
        return nd_count;
    };
    auto link = [&](int a, int b, int c) {
        adj[a].eb(b, c);
        adj[b].eb(a, c);
    };
    For(i, 0, n - 1) {
        vector<int> aly(1, 0);
        new_node(x[i], 0);
        for(auto &p:mp) {
            if(p.F > h[i]) break;
            aly.eb(p.F);
            int id = new_node(x[i], p.F);
            link(id, p.S.S, x[i] - p.S.F);
            p.S.F = x[i];
            p.S.S = id;
        }
        for(auto &y:ed[i]) {
            mp.erase(y);
        }
        for(auto &y:st[i]) {
            aly.eb(y);
            int id = new_node(x[i], y);
            mp[y] = pii(x[i], id);
        }
        sort(all(aly));
        // for(auto &p:aly) cout << p << " ";
        // cout << "\n";
        For(j, 1, sz(aly) - 1) {
            int y1 = aly[j - 1];
            int y2 = aly[j];
            int nd1 = new_node(x[i], y1);
            int nd2 = new_node(x[i], y2);
            link(nd1, nd2, y2 - y1);
            // cout << nd1 << " " << nd2 << " " << y2 - y1 << "\n";
        }
    }
    // for(auto &i:nodes) {
    //     cout << "(" << i.F.F << ", " << i.F.S << ") = " << i.S << "\n";
    // }
    memset(dist, -1, sizeof(dist));
    priority_queue<pii, vector<pii>, greater<pii>> pq; // dist, id
    pq.emplace(0, new_node(x[s], 0));
    int target = new_node(x[g], 0);
    while(!pq.empty()) {
        int d, id;
        tie(d, id) = pq.top(); pq.pop();
        if(dist[id] != -1) continue;
        if(id == target) return d;
        dist[id] = d;
        // cout << id << " " << d << "\n";
        for(auto &e:adj[id]) if(dist[e.F] == -1) {
            pq.emplace(d + e.S, e.F);
        }
    }
    return -1;
}

long long min_distance(Vi x, Vi h, Vi l, Vi r, Vi y, int32_t s, int32_t g) {
	n = sz(x);
    m = sz(l);
    // return solve_1n(x, h, l, r, y);
    return solve(x, h, l, r, y, s, g);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 67532 KB Output is correct
2 Correct 35 ms 67604 KB Output is correct
3 Correct 34 ms 67528 KB Output is correct
4 Correct 33 ms 67564 KB Output is correct
5 Correct 32 ms 67584 KB Output is correct
6 Correct 32 ms 67668 KB Output is correct
7 Correct 33 ms 67576 KB Output is correct
8 Correct 32 ms 67668 KB Output is correct
9 Correct 32 ms 67580 KB Output is correct
10 Correct 33 ms 67708 KB Output is correct
11 Correct 32 ms 67540 KB Output is correct
12 Correct 36 ms 67568 KB Output is correct
13 Correct 33 ms 67648 KB Output is correct
14 Correct 33 ms 67620 KB Output is correct
15 Correct 32 ms 67636 KB Output is correct
16 Correct 33 ms 67568 KB Output is correct
17 Correct 33 ms 67668 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 67560 KB Output is correct
2 Correct 33 ms 67540 KB Output is correct
3 Correct 622 ms 174396 KB Output is correct
4 Correct 814 ms 189568 KB Output is correct
5 Correct 612 ms 172336 KB Output is correct
6 Correct 542 ms 160844 KB Output is correct
7 Correct 621 ms 172388 KB Output is correct
8 Correct 822 ms 202628 KB Output is correct
9 Correct 659 ms 171188 KB Output is correct
10 Correct 1138 ms 230816 KB Output is correct
11 Correct 415 ms 129612 KB Output is correct
12 Correct 290 ms 118208 KB Output is correct
13 Correct 995 ms 214104 KB Output is correct
14 Correct 299 ms 113740 KB Output is correct
15 Correct 303 ms 115832 KB Output is correct
16 Correct 316 ms 116960 KB Output is correct
17 Correct 297 ms 115224 KB Output is correct
18 Correct 430 ms 124204 KB Output is correct
19 Correct 45 ms 69760 KB Output is correct
20 Correct 167 ms 90376 KB Output is correct
21 Correct 263 ms 113164 KB Output is correct
22 Correct 287 ms 117328 KB Output is correct
23 Correct 411 ms 129584 KB Output is correct
24 Correct 306 ms 116920 KB Output is correct
25 Correct 271 ms 115076 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 83540 KB Output is correct
2 Runtime error 2029 ms 678540 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 83540 KB Output is correct
2 Runtime error 2029 ms 678540 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 67532 KB Output is correct
2 Correct 35 ms 67604 KB Output is correct
3 Correct 34 ms 67528 KB Output is correct
4 Correct 33 ms 67564 KB Output is correct
5 Correct 32 ms 67584 KB Output is correct
6 Correct 32 ms 67668 KB Output is correct
7 Correct 33 ms 67576 KB Output is correct
8 Correct 32 ms 67668 KB Output is correct
9 Correct 32 ms 67580 KB Output is correct
10 Correct 33 ms 67708 KB Output is correct
11 Correct 32 ms 67540 KB Output is correct
12 Correct 36 ms 67568 KB Output is correct
13 Correct 33 ms 67648 KB Output is correct
14 Correct 33 ms 67620 KB Output is correct
15 Correct 32 ms 67636 KB Output is correct
16 Correct 33 ms 67568 KB Output is correct
17 Correct 33 ms 67668 KB Output is correct
18 Correct 32 ms 67560 KB Output is correct
19 Correct 33 ms 67540 KB Output is correct
20 Correct 622 ms 174396 KB Output is correct
21 Correct 814 ms 189568 KB Output is correct
22 Correct 612 ms 172336 KB Output is correct
23 Correct 542 ms 160844 KB Output is correct
24 Correct 621 ms 172388 KB Output is correct
25 Correct 822 ms 202628 KB Output is correct
26 Correct 659 ms 171188 KB Output is correct
27 Correct 1138 ms 230816 KB Output is correct
28 Correct 415 ms 129612 KB Output is correct
29 Correct 290 ms 118208 KB Output is correct
30 Correct 995 ms 214104 KB Output is correct
31 Correct 299 ms 113740 KB Output is correct
32 Correct 303 ms 115832 KB Output is correct
33 Correct 316 ms 116960 KB Output is correct
34 Correct 297 ms 115224 KB Output is correct
35 Correct 430 ms 124204 KB Output is correct
36 Correct 45 ms 69760 KB Output is correct
37 Correct 167 ms 90376 KB Output is correct
38 Correct 263 ms 113164 KB Output is correct
39 Correct 287 ms 117328 KB Output is correct
40 Correct 411 ms 129584 KB Output is correct
41 Correct 306 ms 116920 KB Output is correct
42 Correct 271 ms 115076 KB Output is correct
43 Correct 121 ms 83540 KB Output is correct
44 Runtime error 2029 ms 678540 KB Execution killed with signal 6
45 Halted 0 ms 0 KB -