oj.uz

Submission #725936

# Submission time Handle Problem Language Result Execution time Memory
725936 2023-04-18T09:04:13 Z PixelCat Sky Walking (IOI19_walk) C++14
15 / 100
 242 ms 74464 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;
    };
    set<int> pending;
    For(i, 1, n - 2) {
        set<int> upd;
        for(auto &j:st[i]) pending.insert(j);
        if(eval(h[i], h[i]) >= INF) continue;
        for(auto &j:pending) {
            int k = eval(j, h[i]);
            mp[j] = k;
            upd.insert(j);
        }
        pending.clear();
        for(auto &j:ed[i]) if(!upd.count(j)) {
            if(mp.count(j)) mp.erase(j);
            else pending.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 51940 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 51948 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 59 ms 54928 KB Output is correct
2 Correct 141 ms 56944 KB Output is correct
3 Correct 150 ms 57976 KB Output is correct
4 Correct 192 ms 62356 KB Output is correct
5 Correct 242 ms 66696 KB Output is correct
6 Correct 213 ms 64924 KB Output is correct
7 Correct 98 ms 59332 KB Output is correct
8 Correct 122 ms 64420 KB Output is correct
9 Correct 176 ms 66184 KB Output is correct
10 Correct 150 ms 67256 KB Output is correct
11 Correct 39 ms 53500 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 54928 KB Output is correct
2 Correct 141 ms 56944 KB Output is correct
3 Correct 150 ms 57976 KB Output is correct
4 Correct 192 ms 62356 KB Output is correct
5 Correct 242 ms 66696 KB Output is correct
6 Correct 213 ms 64924 KB Output is correct
7 Correct 98 ms 59332 KB Output is correct
8 Correct 122 ms 64420 KB Output is correct
9 Correct 176 ms 66184 KB Output is correct
10 Correct 150 ms 67256 KB Output is correct
11 Correct 39 ms 53500 KB Output is correct
12 Correct 135 ms 57932 KB Output is correct
13 Correct 155 ms 66728 KB Output is correct
14 Correct 227 ms 66836 KB Output is correct
15 Correct 146 ms 62420 KB Output is correct
16 Correct 149 ms 62420 KB Output is correct
17 Correct 156 ms 62480 KB Output is correct
18 Correct 146 ms 62592 KB Output is correct
19 Correct 153 ms 62488 KB Output is correct
20 Correct 109 ms 59384 KB Output is correct
21 Correct 56 ms 54732 KB Output is correct
22 Incorrect 149 ms 74464 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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