oj.uz

Submission #1071457

# Submission time Handle Problem Language Result Execution time Memory
1071457 2024-08-23T07:31:48 Z becaido Sky Walking (IOI19_walk) C++17
33 / 100
 774 ms 93660 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "walk.h"
#else
#include "grader.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1e5 + 5;

int n, m, s, e, sz;
vector<int> y[SIZE];
int x[SIZE], h[SIZE];
vector<pair<int, int>> P, Q;
tuple<int, int, int> a[SIZE];

int get_id(int i, int y) {
    return lower_bound(P.begin(), P.end(), make_pair(i, y)) - P.begin() + 1;
}

set<pair<int, int>> seg;
void split(int p) {
    auto it = prev(seg.lower_bound({p + 1, 0}));
    if (it->F != p) seg.emplace(p, it->S);
}
void upd(int l, int r, int y) {
    split(l), split(r + 1);
    for (auto it = seg.lower_bound({l, 0}); it->F <= r; it = seg.erase(it));
    seg.emplace(l, y);
}
int get_h(int p) {
    auto it = prev(seg.lower_bound({p + 1, 0}));
    return it->S;
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g) {
    n = _x.size(), m = _l.size();
    s = _s + 1, e = _g + 1;
    FOR (i, 1, n) {
        x[i] = _x[i - 1];
        h[i] = _h[i - 1];
    }
    FOR (i, 1, m) {
        _l[i - 1]++, _r[i - 1]++;
        a[i] = {_y[i - 1], _l[i - 1], _r[i - 1]};
    }

    seg.emplace(1, 0);
    seg.emplace(n + 1, 0);
    sort(a + 1, a + m + 1);
    FOR (i, 1, n) y[i].pb(0);
    FOR (i, 1, m) {
        auto [h, l, r] = a[i];
        y[l].pb(h), y[r].pb(h);
        y[l].pb(get_h(l));
        y[r].pb(get_h(r));
        upd(l, r, h);
    }
    seg.clear();
    seg.emplace(1, inf);
    seg.emplace(n + 1, inf);
    for (int i = m; i >= 1; i--) {
        auto [h, l, r] = a[i];
        int hl = get_h(l), hr = get_h(r);
        if (hl != inf) y[l].pb(hl);
        if (hr != inf) y[r].pb(hr);
        upd(l, r, h);
    }

    FOR (i, 1, n) {
        sort(y[i].begin(), y[i].end());
        y[i].erase(unique(y[i].begin(), y[i].end()), y[i].end());
        for (int iy : y[i]) P.pb(i, iy), Q.pb(iy, i);
        sz += y[i].size();
    }
    sort(Q.begin(), Q.end());

    vector<ll> dis(sz + 1, INF);
    vector<vector<pair<int, int>>> adj(sz + 1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
        int u = get_id(i, y[i][j]), v = get_id(i, y[i][j + 1]);
        adj[u].pb(v, y[i][j + 1] - y[i][j]);
        adj[v].pb(u, y[i][j + 1] - y[i][j]);
    }
    FOR (i, 1, m) {
        auto [h, l, r] = a[i];
        int j = lower_bound(Q.begin(), Q.end(), make_pair(h, l)) - Q.begin();
        while (Q[j].S < r) {
            int u = get_id(Q[j].S, h), v = get_id(Q[j + 1].S, h), d = x[Q[j + 1].S] - x[Q[j].S];
            adj[u].pb(v, d);
            adj[v].pb(u, d);
            j++;
        }
    }
    s = get_id(s, 0), e = get_id(e, 0);
    pq.emplace(dis[s] = 0, s);
    while (pq.size()) {
        auto [d, pos] = pq.top();
        pq.pop();
        if (d > dis[pos]) continue;
        for (auto [np, w] : adj[pos]) if (d + w < dis[np]) {
            pq.emplace(dis[np] = d + w, np);
        }
    }
    return dis[e] == INF ? -1 : dis[e];
}

/*
in1
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
out1
27

in2
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
out2
21
*/

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:102:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     FOR (i, 1, n) for (int j = 0; j + 1 < y[i].size(); j++) {
      |                                   ~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 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 83 ms 15384 KB Output is correct
2 Correct 536 ms 69020 KB Output is correct
3 Correct 585 ms 73876 KB Output is correct
4 Correct 774 ms 90344 KB Output is correct
5 Correct 768 ms 91288 KB Output is correct
6 Correct 692 ms 85400 KB Output is correct
7 Correct 417 ms 53332 KB Output is correct
8 Correct 437 ms 50600 KB Output is correct
9 Correct 691 ms 80392 KB Output is correct
10 Correct 278 ms 56236 KB Output is correct
11 Correct 14 ms 10192 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15384 KB Output is correct
2 Correct 536 ms 69020 KB Output is correct
3 Correct 585 ms 73876 KB Output is correct
4 Correct 774 ms 90344 KB Output is correct
5 Correct 768 ms 91288 KB Output is correct
6 Correct 692 ms 85400 KB Output is correct
7 Correct 417 ms 53332 KB Output is correct
8 Correct 437 ms 50600 KB Output is correct
9 Correct 691 ms 80392 KB Output is correct
10 Correct 278 ms 56236 KB Output is correct
11 Correct 14 ms 10192 KB Output is correct
12 Correct 619 ms 72752 KB Output is correct
13 Correct 604 ms 85144 KB Output is correct
14 Correct 705 ms 91036 KB Output is correct
15 Correct 523 ms 78152 KB Output is correct
16 Correct 527 ms 80644 KB Output is correct
17 Correct 637 ms 93660 KB Output is correct
18 Correct 510 ms 77284 KB Output is correct
19 Correct 538 ms 78392 KB Output is correct
20 Correct 358 ms 50856 KB Output is correct
21 Correct 33 ms 16352 KB Output is correct
22 Correct 574 ms 76184 KB Output is correct
23 Correct 565 ms 75056 KB Output is correct
24 Correct 460 ms 61608 KB Output is correct
25 Correct 540 ms 67876 KB Output is correct
26 Correct 398 ms 60248 KB Output is correct
27 Correct 711 ms 88096 KB Output is correct
28 Correct 650 ms 89176 KB Output is correct
29 Correct 658 ms 84656 KB Output is correct
30 Correct 398 ms 53340 KB Output is correct
31 Correct 597 ms 79568 KB Output is correct
32 Correct 244 ms 50644 KB Output is correct
33 Correct 273 ms 57572 KB Output is correct
34 Correct 295 ms 58028 KB Output is correct
35 Correct 329 ms 60276 KB Output is correct
36 Correct 339 ms 53928 KB Output is correct
37 Correct 236 ms 47248 KB Output is correct
38 Correct 285 ms 62212 KB Output is correct
39 Correct 320 ms 63448 KB Output is correct
40 Correct 268 ms 56488 KB Output is correct
41 Correct 283 ms 51380 KB Output is correct

Subtask #5
0 / 43.0

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