oj.uz

Submission #725930

# Submission time Handle Problem Language Result Execution time Memory
725930 2023-04-18T08:57:41 Z PixelCat Sky Walking (IOI19_walk) C++14
15 / 100
 187 ms 70572 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 38 ms 51884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 51924 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 63 ms 54900 KB Output is correct
2 Correct 146 ms 56936 KB Output is correct
3 Correct 143 ms 59708 KB Output is correct
4 Correct 185 ms 66036 KB Output is correct
5 Correct 179 ms 70572 KB Output is correct
6 Correct 170 ms 68492 KB Output is correct
7 Correct 108 ms 62004 KB Output is correct
8 Correct 144 ms 68088 KB Output is correct
9 Correct 175 ms 70036 KB Output is correct
10 Correct 127 ms 69068 KB Output is correct
11 Correct 44 ms 53836 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 54900 KB Output is correct
2 Correct 146 ms 56936 KB Output is correct
3 Correct 143 ms 59708 KB Output is correct
4 Correct 185 ms 66036 KB Output is correct
5 Correct 179 ms 70572 KB Output is correct
6 Correct 170 ms 68492 KB Output is correct
7 Correct 108 ms 62004 KB Output is correct
8 Correct 144 ms 68088 KB Output is correct
9 Correct 175 ms 70036 KB Output is correct
10 Correct 127 ms 69068 KB Output is correct
11 Correct 44 ms 53836 KB Output is correct
12 Correct 129 ms 59692 KB Output is correct
13 Correct 153 ms 66100 KB Output is correct
14 Correct 187 ms 70512 KB Output is correct
15 Correct 150 ms 65868 KB Output is correct
16 Correct 146 ms 66152 KB Output is correct
17 Correct 145 ms 66172 KB Output is correct
18 Correct 130 ms 65916 KB Output is correct
19 Correct 135 ms 66124 KB Output is correct
20 Correct 107 ms 61892 KB Output is correct
21 Incorrect 56 ms 56288 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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