oj.uz

Submission #434251

# Submission time Handle Problem Language Result Execution time Memory
434251 2021-06-20T19:41:52 Z emil_physmath Sky Walking (IOI19_walk) C++17
39 / 100
 4000 ms 406044 KB 
#define BUGO(x) cerr << #x << " -> " << (x) << endl;
#include "walk.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
using llong = long long;

vector<pair<int, int>> nei[6900'000];
llong dist[6900'000];

const llong inf = 69'000'000'000'000'000LL;
llong Dijkstra(int s, int e)
{
    fill(dist, dist + 6900'000, inf);
    priority_queue<pair<llong, int>> q;
    q.push({dist[s] = 0, s});
    while (q.size())
    {
        int v = q.top().second;
        llong d = -q.top().first;
        q.pop();
        if (dist[v] != d) continue;
        for (auto to: nei[v])
            if (d + to.second < dist[to.first])
                q.push({-(dist[to.first] = d + to.second), to.first});
    }
    return dist[e] == inf ? -1 : dist[e];
}

map<int, int> nodeOf[100'000];
llong dp[100'000];
struct Comp {
    static vector<int>* h_;
    bool operator()(int l, int r) const {
        return h_->at(l) < h_->at(r);
    }
};
vector<int>* Comp::h_;
long long min_distance(std::vector<int> x, std::vector<int> y, std::vector<int> l, std::vector<int> r,
std::vector<int> h, int s, int e) {
    int n = x.size();
    int m = l.size();
    if ((n <= 50 && m <= 50) || y != vector<int>(n, y[0]))
    {
        int nodes = 0;
        for (int i = 0; i < n; ++i)
            nodeOf[i][y[i]] = nodes++;
        nodeOf[s][0] = nodes++;
        nodeOf[e][0] = nodes++;
        vector<int> towers(n);
        iota(towers.begin(), towers.end(), 0);
        sort(towers.begin(), towers.end(), [&](int l, int r) {
            return y[l] < y[r];
        });
        vector<int> bridges(m);
        iota(bridges.begin(), bridges.end(), 0);
        sort(bridges.begin(), bridges.end(), [&](int l, int r) {
            return h[l] < h[r];
        });
        set<int> activeTowers;
        for (int tch = m - 1; tch >= 0; --tch)
        {
            int j = bridges[tch];
            while (towers.size() && y[towers.back()] >= h[j]) {
                activeTowers.insert(towers.back());
                towers.pop_back();
            }
            int lt = -1;
            for (auto it = activeTowers.lower_bound(l[j]); it != activeTowers.end() && *it <= r[j]; ++it)
            {
                int i = *it;
                if (!nodeOf[i].count(h[j]))
                    nodeOf[i][h[j]] = nodes++;
                if (lt != -1) {
                    int u = nodeOf[i][h[j]];
                    int v = nodeOf[lt][h[j]];
                    nei[u].push_back({v, x[i] - x[lt]});
                    nei[v].push_back({u, x[i] - x[lt]});
                }
                lt = i;
            }
        }
        for (int i = 0; i < n; ++i)
        {
            int ltHei = -1;
            for (auto [hei, node]: nodeOf[i])
            {
                if (ltHei != -1) {
                    int u = nodeOf[i][ltHei];
                    int v = node;
                    nei[u].push_back({v, hei - ltHei});
                    nei[v].push_back({u, hei - ltHei});
                }
                ltHei = hei;
            }
        }
        return Dijkstra(n, n + 1);
    }

    l.push_back(-1);
    r.push_back(0);
    h.push_back(0);
    ++m;
    fill(dp, dp + m, inf);
    dp[m - 1] = 0;
    vector<int> bridges(m);
    iota(bridges.begin(), bridges.end(), 0);
    sort(bridges.begin(), bridges.end(), [&r](int i, int j) {
        return r[i] < r[j];
    });

    vector<pair<int, int>> bridgesUpd;
    for (int j = 0; j < m; ++j) {
        bridgesUpd.push_back({l[j], j});
        bridgesUpd.push_back({r[j], -j});
    }
    sort(bridgesUpd.begin(), bridgesUpd.end());

    Comp::h_ = &h;
    set<int, Comp> activeBridges;
    int j = 0;
    for (int i: bridges)
    {
        if (dp[i] == inf) continue;
        while (j < bridgesUpd.size() && bridgesUpd[j].first <= r[i]) {
            // BUGO(bridgesUpd[j].first)
            int upd = bridgesUpd[j++].second;
            if (upd > 0 || (!upd && !activeBridges.count(upd))) activeBridges.insert(upd);
            else activeBridges.erase(-upd);
        }
        auto it = activeBridges.lower_bound(i);
        if (it != activeBridges.end())
            dp[*it] = min(dp[*it], dp[i] + x[r[*it]] - x[r[i]] + h[*it] - h[i]);
        if (it != activeBridges.begin()) {
            --it;
            dp[*it] = min(dp[*it], dp[i] + x[r[*it]] - x[r[i]] + h[i] - h[*it]);
        }
    }
    llong ans = inf;
    for (int j = 0; j < m; ++j)
        if (r[j] == n - 1)
            ans = min(ans, dp[j] + h[j]);
    return ans == inf ? -1 : ans;
}

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:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         while (j < bridgesUpd.size() && bridgesUpd[j].first <= r[i]) {
      |                ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 220980 KB Output is correct
2 Correct 131 ms 220908 KB Output is correct
3 Correct 129 ms 220988 KB Output is correct
4 Correct 132 ms 220996 KB Output is correct
5 Correct 132 ms 221064 KB Output is correct
6 Correct 132 ms 221032 KB Output is correct
7 Correct 130 ms 220996 KB Output is correct
8 Correct 140 ms 221036 KB Output is correct
9 Correct 138 ms 221024 KB Output is correct
10 Correct 129 ms 221072 KB Output is correct
11 Correct 128 ms 220960 KB Output is correct
12 Correct 127 ms 220976 KB Output is correct
13 Correct 128 ms 220996 KB Output is correct
14 Correct 131 ms 221020 KB Output is correct
15 Correct 128 ms 220976 KB Output is correct
16 Correct 133 ms 220940 KB Output is correct
17 Correct 129 ms 221216 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 220972 KB Output is correct
2 Correct 128 ms 220984 KB Output is correct
3 Correct 1328 ms 308252 KB Output is correct
4 Correct 1181 ms 319384 KB Output is correct
5 Correct 779 ms 306808 KB Output is correct
6 Correct 726 ms 296240 KB Output is correct
7 Correct 786 ms 306796 KB Output is correct
8 Correct 1687 ms 333340 KB Output is correct
9 Correct 934 ms 304372 KB Output is correct
10 Correct 1531 ms 357036 KB Output is correct
11 Correct 707 ms 268008 KB Output is correct
12 Correct 530 ms 255388 KB Output is correct
13 Correct 1315 ms 340920 KB Output is correct
14 Correct 382 ms 249756 KB Output is correct
15 Correct 369 ms 246056 KB Output is correct
16 Correct 384 ms 248600 KB Output is correct
17 Correct 412 ms 247732 KB Output is correct
18 Correct 382 ms 253328 KB Output is correct
19 Correct 134 ms 222236 KB Output is correct
20 Correct 215 ms 233008 KB Output is correct
21 Correct 399 ms 246692 KB Output is correct
22 Correct 378 ms 245984 KB Output is correct
23 Correct 383 ms 255580 KB Output is correct
24 Correct 373 ms 247260 KB Output is correct
25 Correct 421 ms 247136 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 170192 KB Output is correct
2 Correct 221 ms 173060 KB Output is correct
3 Correct 218 ms 175344 KB Output is correct
4 Correct 259 ms 178840 KB Output is correct
5 Correct 285 ms 182348 KB Output is correct
6 Correct 292 ms 179836 KB Output is correct
7 Correct 184 ms 174884 KB Output is correct
8 Correct 201 ms 178700 KB Output is correct
9 Correct 270 ms 180108 KB Output is correct
10 Correct 224 ms 179352 KB Output is correct
11 Correct 110 ms 168748 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 170192 KB Output is correct
2 Correct 221 ms 173060 KB Output is correct
3 Correct 218 ms 175344 KB Output is correct
4 Correct 259 ms 178840 KB Output is correct
5 Correct 285 ms 182348 KB Output is correct
6 Correct 292 ms 179836 KB Output is correct
7 Correct 184 ms 174884 KB Output is correct
8 Correct 201 ms 178700 KB Output is correct
9 Correct 270 ms 180108 KB Output is correct
10 Correct 224 ms 179352 KB Output is correct
11 Correct 110 ms 168748 KB Output is correct
12 Execution timed out 4061 ms 406044 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 220980 KB Output is correct
2 Correct 131 ms 220908 KB Output is correct
3 Correct 129 ms 220988 KB Output is correct
4 Correct 132 ms 220996 KB Output is correct
5 Correct 132 ms 221064 KB Output is correct
6 Correct 132 ms 221032 KB Output is correct
7 Correct 130 ms 220996 KB Output is correct
8 Correct 140 ms 221036 KB Output is correct
9 Correct 138 ms 221024 KB Output is correct
10 Correct 129 ms 221072 KB Output is correct
11 Correct 128 ms 220960 KB Output is correct
12 Correct 127 ms 220976 KB Output is correct
13 Correct 128 ms 220996 KB Output is correct
14 Correct 131 ms 221020 KB Output is correct
15 Correct 128 ms 220976 KB Output is correct
16 Correct 133 ms 220940 KB Output is correct
17 Correct 129 ms 221216 KB Output is correct
18 Correct 130 ms 220972 KB Output is correct
19 Correct 128 ms 220984 KB Output is correct
20 Correct 1328 ms 308252 KB Output is correct
21 Correct 1181 ms 319384 KB Output is correct
22 Correct 779 ms 306808 KB Output is correct
23 Correct 726 ms 296240 KB Output is correct
24 Correct 786 ms 306796 KB Output is correct
25 Correct 1687 ms 333340 KB Output is correct
26 Correct 934 ms 304372 KB Output is correct
27 Correct 1531 ms 357036 KB Output is correct
28 Correct 707 ms 268008 KB Output is correct
29 Correct 530 ms 255388 KB Output is correct
30 Correct 1315 ms 340920 KB Output is correct
31 Correct 382 ms 249756 KB Output is correct
32 Correct 369 ms 246056 KB Output is correct
33 Correct 384 ms 248600 KB Output is correct
34 Correct 412 ms 247732 KB Output is correct
35 Correct 382 ms 253328 KB Output is correct
36 Correct 134 ms 222236 KB Output is correct
37 Correct 215 ms 233008 KB Output is correct
38 Correct 399 ms 246692 KB Output is correct
39 Correct 378 ms 245984 KB Output is correct
40 Correct 383 ms 255580 KB Output is correct
41 Correct 373 ms 247260 KB Output is correct
42 Correct 421 ms 247136 KB Output is correct
43 Correct 154 ms 170192 KB Output is correct
44 Correct 221 ms 173060 KB Output is correct
45 Correct 218 ms 175344 KB Output is correct
46 Correct 259 ms 178840 KB Output is correct
47 Correct 285 ms 182348 KB Output is correct
48 Correct 292 ms 179836 KB Output is correct
49 Correct 184 ms 174884 KB Output is correct
50 Correct 201 ms 178700 KB Output is correct
51 Correct 270 ms 180108 KB Output is correct
52 Correct 224 ms 179352 KB Output is correct
53 Correct 110 ms 168748 KB Output is correct
54 Execution timed out 4061 ms 406044 KB Time limit exceeded
55 Halted 0 ms 0 KB -