oj.uz

Submission #890241

# Submission time Handle Problem Language Result Execution time Memory
890241 2023-12-20T18:30:26 Z vjudge1 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 824748 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<ll>;
using ii = pair<ll, ll>;

struct Dijkstra {
    vector<vector<ii> > L;
    ll n;

    Dijkstra(ll N) : n(N), L(N) {}

    void add_edge(ll u, ll v, ll w) {
        L[u].push_back({v, w});
        L[v].push_back({u, w});
    }

    ll dist(ll s, ll t) {
        const ll INF = 1e18;
        vector<ll> D(n, INF);
        D[s] = 0;
        priority_queue<pair<ll, ll> > PQ;
        PQ.push({0, s});
        while(!PQ.empty()) {
            ll u = PQ.top().second;
            ll d = - PQ.top().first;
            PQ.pop();
            if(D[u] != d) continue;
            for(auto [it, w] : L[u]) {
                if(D[it] > D[u] + w) {
                    D[it] = D[u] + w;
                    PQ.push({-D[it], it});
                }
            }
        }
        if(D[t] == INF) D[t] = -1;
        return D[t];
    }
};

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    ll n = x.size();
    ll tmr = 0;
    vector<vector<pair<ll, ll> > > Noduri(n); /// perechi(id, h)
    vector<tuple<ll, ll, ll> > E;
    for(ll i = 0; i < n; ++i) {
        Noduri[i].push_back({tmr++, 0});
    }
    for(ll i = 0; i < l.size(); ++i) {
        ll ult = -1;
        for(ll j = l[i]; j <= r[i]; ++j) {
            if(h[j] < y[i]) continue;
            else {
                Noduri[j].push_back({tmr++, y[i]});
                if(ult != -1) {
                    E.emplace_back(tmr - 1, Noduri[ult].back().first, x[j] - x[ult]);
                }
                ult = j;
            }
        }
    }

    Dijkstra Sol(tmr);

    for(auto [u, v, w] : E)
        Sol.add_edge(u, v, w);

    for(ll i = 0; i < n; ++i) {
        sort(Noduri[i].begin(), Noduri[i].end(), [&](auto a, auto b) {return a.second < b.second;});
        for(ll j = 0; j + 1 < Noduri[i].size(); ++j) {
            Sol.add_edge(Noduri[i][j].first, Noduri[i][j + 1].first,
                    Noduri[i][j + 1].second - Noduri[i][j].second);
        }
    }
	return Sol.dist(Noduri[s][0].first, Noduri[g][0].first);
}

Compilation message

walk.cpp: In constructor 'Dijkstra::Dijkstra(ll)':
walk.cpp:12:8: warning: 'Dijkstra::n' will be initialized after [-Wreorder]
   12 |     ll n;
      |        ^
walk.cpp:11:25: warning:   'std::vector<std::vector<std::pair<long long int, long long int> > > Dijkstra::L' [-Wreorder]
   11 |     vector<vector<ii> > L;
      |                         ^
walk.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     Dijkstra(ll N) : n(N), L(N) {}
      |     ^~~~~~~~
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:52:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(ll i = 0; i < l.size(); ++i) {
      |                   ~~^~~~~~~~~~
walk.cpp:73:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(ll j = 0; j + 1 < Noduri[i].size(); ++j) {
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 372 KB Output is correct
17 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 554 ms 117832 KB Output is correct
4 Correct 563 ms 132228 KB Output is correct
5 Correct 389 ms 113052 KB Output is correct
6 Correct 1012 ms 101108 KB Output is correct
7 Correct 383 ms 113232 KB Output is correct
8 Correct 703 ms 148024 KB Output is correct
9 Correct 383 ms 110316 KB Output is correct
10 Correct 796 ms 178920 KB Output is correct
11 Correct 274 ms 64480 KB Output is correct
12 Correct 182 ms 47860 KB Output is correct
13 Correct 696 ms 159012 KB Output is correct
14 Correct 3618 ms 45440 KB Output is correct
15 Correct 1924 ms 46852 KB Output is correct
16 Correct 251 ms 46992 KB Output is correct
17 Correct 275 ms 45776 KB Output is correct
18 Execution timed out 4024 ms 13968 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19720 KB Output is correct
2 Execution timed out 4059 ms 824748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19720 KB Output is correct
2 Execution timed out 4059 ms 824748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 372 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 554 ms 117832 KB Output is correct
21 Correct 563 ms 132228 KB Output is correct
22 Correct 389 ms 113052 KB Output is correct
23 Correct 1012 ms 101108 KB Output is correct
24 Correct 383 ms 113232 KB Output is correct
25 Correct 703 ms 148024 KB Output is correct
26 Correct 383 ms 110316 KB Output is correct
27 Correct 796 ms 178920 KB Output is correct
28 Correct 274 ms 64480 KB Output is correct
29 Correct 182 ms 47860 KB Output is correct
30 Correct 696 ms 159012 KB Output is correct
31 Correct 3618 ms 45440 KB Output is correct
32 Correct 1924 ms 46852 KB Output is correct
33 Correct 251 ms 46992 KB Output is correct
34 Correct 275 ms 45776 KB Output is correct
35 Execution timed out 4024 ms 13968 KB Time limit exceeded
36 Halted 0 ms 0 KB -