oj.uz

Submission #580697

# Submission time Handle Problem Language Result Execution time Memory
580697 2022-06-21T16:51:31 Z georgievskiy Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 700808 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sint signed
#define int long long

#define pii pair<int, int>

int min_distance(std::vector<sint> x, std::vector<sint> h, std::vector<sint> l, std::vector<sint> r, std::vector<sint> y, sint ss, sint gg) {
    int n = x.size(), m = l.size();
    vector<vector<pii>> g;
    vector<vector<pii>> c(n);
    int t = 0;
    for (int j = 0; j < m; j++) {
        int last = -1, lp;
        for (int i = l[j]; i <= r[j]; i++) {
            if (h[i] < y[j])
                continue;
            c[i].push_back({y[j], t++});
            g.push_back(vector<pii>());
            if (last != -1) {
                g[lp].push_back({t - 1, x[i] - x[last]});
                g[t - 1].push_back({lp, x[i] - x[last]});
            }
            last = i, lp = t - 1;
        }
    }

    int s = 0, f = 0;
    g.push_back(vector<pii>());
    g.push_back(vector<pii>());
    for (int i = 0; i < n; i++) {
        if (i == ss) {
            s = t;
            c[i].push_back({0, t++});
        }
        if (i == gg) {
            f = t;
            c[i].push_back({0, t++});
        }
        sort(c[i].begin(), c[i].end());
        for (int j = 0; j < (int)c[i].size() - 1; j++) {
            int v = c[i][j].second, u = c[i][j + 1].second;
            int d = c[i][j + 1].first - c[i][j].first;
            g[v].push_back({u, d});
            g[u].push_back({v, d});
        }
    }

    //for (int i = 0; i < t; i++) {
    //    cout << i << " : " ;
    //    for (pii j : g[i])
    //        cout << "{ " << j.first << ' ' << j.second << " }  ";
    //    cout << '\n';
    //}

    int a = 0;

    priority_queue<pii, vector<pii>, greater<pii>> q;
    const int inf = 2e18;

    vector<int> d(t, inf);
    q.push({0, s});

    while (q.size()) {
        int v = q.top().second, dst = q.top().first;
        q.pop();
        if (d[v] != inf)
            continue;
        d[v] = dst;
        for (auto u : g[v]) {
            if (d[u.first] == inf) {
                q.push({dst + u.second, u.first});
            }
        }
    }

    if (d[f] == inf)
        return -1;
    else
        return d[f];
}

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:57:9: warning: unused variable 'a' [-Wunused-variable]
   57 |     int a = 0;
      |         ^

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 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 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 782 ms 102212 KB Output is correct
4 Correct 748 ms 106476 KB Output is correct
5 Correct 536 ms 91844 KB Output is correct
6 Correct 1085 ms 80756 KB Output is correct
7 Correct 444 ms 91888 KB Output is correct
8 Correct 947 ms 128512 KB Output is correct
9 Correct 548 ms 92060 KB Output is correct
10 Correct 1052 ms 148112 KB Output is correct
11 Correct 396 ms 55020 KB Output is correct
12 Correct 186 ms 32368 KB Output is correct
13 Correct 886 ms 131868 KB Output is correct
14 Correct 3480 ms 32104 KB Output is correct
15 Correct 1840 ms 32040 KB Output is correct
16 Correct 277 ms 33736 KB Output is correct
17 Correct 299 ms 32596 KB Output is correct
18 Execution timed out 4089 ms 13768 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 17408 KB Output is correct
2 Execution timed out 4094 ms 700808 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 17408 KB Output is correct
2 Execution timed out 4094 ms 700808 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 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 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 782 ms 102212 KB Output is correct
21 Correct 748 ms 106476 KB Output is correct
22 Correct 536 ms 91844 KB Output is correct
23 Correct 1085 ms 80756 KB Output is correct
24 Correct 444 ms 91888 KB Output is correct
25 Correct 947 ms 128512 KB Output is correct
26 Correct 548 ms 92060 KB Output is correct
27 Correct 1052 ms 148112 KB Output is correct
28 Correct 396 ms 55020 KB Output is correct
29 Correct 186 ms 32368 KB Output is correct
30 Correct 886 ms 131868 KB Output is correct
31 Correct 3480 ms 32104 KB Output is correct
32 Correct 1840 ms 32040 KB Output is correct
33 Correct 277 ms 33736 KB Output is correct
34 Correct 299 ms 32596 KB Output is correct
35 Execution timed out 4089 ms 13768 KB Time limit exceeded
36 Halted 0 ms 0 KB -