oj.uz

Submission #726027

# Submission time Handle Problem Language Result Execution time Memory
726027 2023-04-18T10:28:08 Z PixelCat Sky Walking (IOI19_walk) C++14
33 / 100
 192 ms 69964 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 = 1e18;
 
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);
        }
        // for(auto &p:mp) cout << p.F << " " << p.S << "\n";
        // cout << "\n";
    }
    // 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 51924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 51836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 55544 KB Output is correct
2 Correct 115 ms 58364 KB Output is correct
3 Correct 137 ms 59104 KB Output is correct
4 Correct 170 ms 63500 KB Output is correct
5 Correct 189 ms 67868 KB Output is correct
6 Correct 192 ms 66024 KB Output is correct
7 Correct 108 ms 60556 KB Output is correct
8 Correct 117 ms 65596 KB Output is correct
9 Correct 156 ms 67328 KB Output is correct
10 Correct 125 ms 67284 KB Output is correct
11 Correct 36 ms 53836 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 55544 KB Output is correct
2 Correct 115 ms 58364 KB Output is correct
3 Correct 137 ms 59104 KB Output is correct
4 Correct 170 ms 63500 KB Output is correct
5 Correct 189 ms 67868 KB Output is correct
6 Correct 192 ms 66024 KB Output is correct
7 Correct 108 ms 60556 KB Output is correct
8 Correct 117 ms 65596 KB Output is correct
9 Correct 156 ms 67328 KB Output is correct
10 Correct 125 ms 67284 KB Output is correct
11 Correct 36 ms 53836 KB Output is correct
12 Correct 117 ms 59176 KB Output is correct
13 Correct 166 ms 63620 KB Output is correct
14 Correct 186 ms 68188 KB Output is correct
15 Correct 169 ms 63660 KB Output is correct
16 Correct 166 ms 63692 KB Output is correct
17 Correct 132 ms 63692 KB Output is correct
18 Correct 118 ms 63728 KB Output is correct
19 Correct 125 ms 63724 KB Output is correct
20 Correct 100 ms 60464 KB Output is correct
21 Correct 58 ms 55936 KB Output is correct
22 Correct 127 ms 63572 KB Output is correct
23 Correct 159 ms 64000 KB Output is correct
24 Correct 117 ms 65528 KB Output is correct
25 Correct 117 ms 63928 KB Output is correct
26 Correct 122 ms 68112 KB Output is correct
27 Correct 182 ms 69964 KB Output is correct
28 Correct 143 ms 65748 KB Output is correct
29 Correct 180 ms 68340 KB Output is correct
30 Correct 88 ms 61944 KB Output is correct
31 Correct 167 ms 69900 KB Output is correct
32 Correct 112 ms 66844 KB Output is correct
33 Correct 116 ms 68104 KB Output is correct
34 Correct 126 ms 67344 KB Output is correct
35 Correct 157 ms 66024 KB Output is correct
36 Correct 107 ms 65480 KB Output is correct
37 Correct 106 ms 64632 KB Output is correct
38 Correct 110 ms 67192 KB Output is correct
39 Correct 125 ms 68732 KB Output is correct
40 Correct 108 ms 66760 KB Output is correct
41 Correct 113 ms 65296 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 51924 KB Output isn't correct
2 Halted 0 ms 0 KB -