oj.uz

Submission #774882

# Submission time Handle Problem Language Result Execution time Memory
774882 2023-07-06T04:52:55 Z t6twotwo Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 707312 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
    int N = X.size();
    int M = Y.size();
    map<pair<int, int>, int> mp;
    vector<pair<int, int>> p;
    for (int i = 0; i < N; i++) {
        mp[{X[i], 0}] = i;
        p.emplace_back(X[i], 0);
    }
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        for (int j = L[i], k = -1; j <= R[i]; j++) {
            if (H[j] >= Y[i]) {
                int q;
                if (!mp.count({X[j], Y[i]})) {
                    mp[{X[j], Y[i]}] = q = p.size();
                    p.emplace_back(X[j], Y[i]);
                    adj.push_back({});
                } else {
                    q = mp[{X[j], Y[i]}];
                }
                if (k != -1) {
                    adj[k].emplace_back(q, X[j] - p[k].first);
                    adj[q].emplace_back(k, X[j] - p[k].first);
                }
                k = q;
            }
        }
    }
    int q = -1;
    for (auto [P, k] : mp) {
        auto [x, y] = P;
        if (q != -1 && p[q].first == x) {
            adj[k].emplace_back(q, y - p[q].second);
            adj[q].emplace_back(k, y - p[q].second);
        }
        q = k;
    }
    int K = adj.size();
    vector<ll> dis(K, -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, x] = pq.top();
        pq.pop();
        if (dis[x] != -1) {
            continue;
        }
        dis[x] = d;
        for (auto [y, z] : adj[x]) {
            pq.emplace(d + z, y);
        }
    }
    return dis[g];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 244 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1173 ms 127788 KB Output is correct
4 Correct 973 ms 141904 KB Output is correct
5 Correct 636 ms 122916 KB Output is correct
6 Correct 1033 ms 108824 KB Output is correct
7 Correct 613 ms 122976 KB Output is correct
8 Correct 1521 ms 163916 KB Output is correct
9 Correct 692 ms 120724 KB Output is correct
10 Correct 1432 ms 196172 KB Output is correct
11 Correct 527 ms 69788 KB Output is correct
12 Correct 278 ms 49692 KB Output is correct
13 Correct 1186 ms 171880 KB Output is correct
14 Correct 2794 ms 47736 KB Output is correct
15 Correct 1556 ms 48920 KB Output is correct
16 Correct 395 ms 50560 KB Output is correct
17 Correct 344 ms 48272 KB Output is correct
18 Execution timed out 4082 ms 26104 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13440 KB Output is correct
2 Execution timed out 4111 ms 707312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13440 KB Output is correct
2 Execution timed out 4111 ms 707312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 244 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1173 ms 127788 KB Output is correct
21 Correct 973 ms 141904 KB Output is correct
22 Correct 636 ms 122916 KB Output is correct
23 Correct 1033 ms 108824 KB Output is correct
24 Correct 613 ms 122976 KB Output is correct
25 Correct 1521 ms 163916 KB Output is correct
26 Correct 692 ms 120724 KB Output is correct
27 Correct 1432 ms 196172 KB Output is correct
28 Correct 527 ms 69788 KB Output is correct
29 Correct 278 ms 49692 KB Output is correct
30 Correct 1186 ms 171880 KB Output is correct
31 Correct 2794 ms 47736 KB Output is correct
32 Correct 1556 ms 48920 KB Output is correct
33 Correct 395 ms 50560 KB Output is correct
34 Correct 344 ms 48272 KB Output is correct
35 Execution timed out 4082 ms 26104 KB Time limit exceeded
36 Halted 0 ms 0 KB -